Encontrar todas as permutações únicas de uma string sem gerar duplicatas

Encontrar todas as permutações de uma string é por um algoritmo bem conhecido Steinhaus-Johnson-Trotter. Mas se a string contiver os caracteres repetidos, como
AABB,
então as possíveis combinações únicas serão 4! / (2! * 2!) = 6

Uma maneira de conseguir isso é que podemos armazená-lo em uma matriz ou mais e, em seguida, remover as duplicatas.

Existe alguma maneira mais simples de modificar o algoritmo de Johnson, para que nunca geremos as permutações duplicadas. (Da maneira mais eficiente)

Use o seguinte 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 você vê, é muito fácil

Eu acho que esse problema é essencialmente o problema de gerar permutações multiset . este artigo parece ser relevante: JF Korsh PS LaFollette. Geração de array sem loop de permutações multiset. The Computer Journal, 47 (5): 612-621, 2004.

Do resumo: Este artigo apresenta um algoritmo sem loop para gerar todas as permutações de um multiset. Cada um é obtido de seu antecessor fazendo uma transposição. Ele difere dos algoritmos anteriores usando uma matriz para as permutações, mas requerendo armazenamento apenas linear em seu comprimento.

Primeiro converta a string em um conjunto de caracteres únicos e números de ocorrências, por exemplo, BANANA -> (3, A), (1, B), (2, N). (Isso pode ser feito classificando a string e agrupando as letras). Em seguida, para cada letra do conjunto, coloque essa letra em todas as permutações do conjunto com uma letra menor (observe a recursion). Continuando o exemplo “BANANA”, temos: permutações ((3, A), (1, B), (2, N)) = A: (permutações ((2, A), (1, B), (2 , N)) ++ B: (permutações ((3, A), (2, N)) ++ N: (permutações ((3, A), (1, B), (1, N))

Aqui está uma implementação funcional em 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)) 

Na minha solução, eu gero recursivamente as opções, tento sempre adicionar todas as letras que não usei quantas vezes eu precisar.

 #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); } 

use exemplo:

 #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 é uma pergunta complicada e precisamos usar a recursion para encontrar todas as permutações de uma String, por exemplo, as permutações “AAB” serão “AAB”, “ABA” e “BAA”. Também precisamos usar Set para garantir que não haja 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