Encontrar todas las permutaciones únicas de una cadena sin generar duplicados

Encontrar todas las permutaciones de una cadena es por un conocido algoritmo Steinhaus-Johnson-Trotter. Pero si la cadena contiene los caracteres repetidos, como
AABB,
entonces las posibles combinaciones únicas serán 4! / (2! * 2!) = 6

Una forma de lograr esto es que podemos almacenarlo en una matriz más o menos y luego eliminar los duplicados.

¿Hay alguna manera más simple de modificar el algoritmo de Johnson, de modo que nunca generemos las permutaciones duplicadas? (De la manera más eficiente)

Use el siguiente algoritmo recursivo:

PermutList Permute(SymArray fullSymArray){ PermutList resultList=empty; for( each symbol A in fullSymArray, but repeated ones take only once) { PermutList lesserPermutList= Permute(fullSymArray without A) for ( each SymArray item in lesserPermutList){ resultList.add("A"+item); } } return resultList; } 

Como ves, es muy fácil

Creo que este problema es esencialmente el problema de generar permutaciones multiset . este documento parece ser relevante: JF Korsh PS LaFollette. Generación de matriz Loopless de permutaciones multiset. The Computer Journal, 47 (5): 612-621, 2004.

Del resumen: este artículo presenta un algoritmo sin bucle para generar todas las permutaciones de un multiset. Cada uno se obtiene de su predecesor haciendo una transposición. Se diferencia de los algoritmos anteriores por usar una matriz para las permutaciones, pero requiere almacenamiento solo lineal en su longitud.

Primero convierta la cadena en un conjunto de caracteres únicos y números de ocurrencia, por ejemplo BANANA -> (3, A), (1, B), (2, N). (Esto se puede hacer clasificando la cadena y agrupando letras). Luego, para cada letra del conjunto, anteceda esa letra a todas las permutaciones del conjunto con una letra menos de esa (tenga en cuenta la recursión). Continuando con el ejemplo “BANANA”, tenemos: permutaciones ((3, A), (1, B), (2, N)) = A: (permutaciones ((2, A), (1, B), (2 , N)) ++ B: (permutaciones ((3, A), (2, N)) ++ N: (permutaciones ((3, A), (1, B), (1, N))

Aquí hay una implementación en funcionamiento en Haskell:

 circularPermutations::[a]->[[a]] circularPermutations xs = helper [] xs [] where helper acc [] _ = acc helper acc (x:xs) ys = helper (((x:xs) ++ ys):acc) xs (ys ++ [x]) nrPermutations::[(Int, a)]->[[a]] nrPermutations x | length x == 1 = [take (fst (head x)) (repeat (snd (head x)))] nrPermutations xs = concat (map helper (circularPermutations xs)) where helper ((1,x):xs) = map ((:) x)(nrPermutations xs) helper ((n,x):xs) = map ((:) x)(nrPermutations ((n - 1, x):xs)) 

En mi solución, genero recursivamente las opciones, bash cada vez agregar todas las letras que no usé tantas veces como sea necesario.

 #include  void fill(char ***adr,int *pos,char *pref) { int i,z=1; //loop on the chars, and check if should use them for (i=0;i<256;i++) if (pos[i]) { int l=strlen(pref); //add the char pref[l]=i; pos[i]--; //call the recursion fill(adr,pos,pref); //delete the char pref[l]=0; pos[i]++; z=0; } if (z) strcpy(*(*adr)++,pref); } void calc(char **arr,const char *str) { int p[256]={0}; int l=strlen(str); char temp[l+1]; for (;l>=0;l--) temp[l]=0; while (*str) p[*str++]++; fill(&arr,p,temp); } 

usar ejemplo:

 #include  #include  int main() { char s[]="AABAF"; char *arr[20]; int i; for (i=0;i<20;i++) arr[i]=malloc(sizeof(s)); calc(arr,s); for (i=0;i<20;i++) printf("%d: %s\n",i,arr[i]); return 0; } 

Esta es una pregunta difícil y necesitamos usar la recursión para encontrar todas las permutaciones de una Cadena, por ejemplo, las permutaciones “AAB” serán “AAB”, “ABA” y “BAA”. También necesitamos usar Set para asegurarnos de que no haya valores duplicados.

 import java.io.*; import java.util.HashSet; import java.util.*; class Permutation { static HashSet set = new HashSet(); public static void main (String[] args) { Scanner in = new Scanner(System.in); System.out.println("Enter :"); StringBuilder str = new StringBuilder(in.nextLine()); NONDuplicatePermutation("",str.toString()); //WITHOUT DUPLICATE PERMUTATION OF STRING System.out.println(set); } public static void NONDuplicatePermutation(String prefix,String str){ //It is nlogn if(str.length()==0){ set.add(prefix); }else{ for(int i=0;i