查找字符串的所有唯一排列而不生成重复项

通过众所周知的Steinhaus-Johnson-Trotter算法找到字符串的所有排列。 但是如果字符串包含重复的字符，例如
AABB，
然后可能的唯一组合将是4！/（2！* 2！）= 6

实现此目的的一种方法是我们可以将其存储在数组中，然后删除重复项。

有没有更简单的方法来修改Johnson算法，因此我们永远不会生成重复的排列。 （以最有效的方式）

Answer 1

使用以下递归算法：

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

如你所见，这很容易

Answer 2

我认为这个问题本质上是生成多集排列的问题。 这篇论文似乎是相关的：JF Korsh PS LaFollette。 无循环数组生成多集排列。 The Computer Journal，47（5）：612-621,2004。

摘要：本文提出了一种无循环算法来生成多集的所有排列。 每个都是通过进行一次换位从其前身获得的。 它与先前的这种算法的不同之处在于，通过使用arrays进行排列，但要求存储的长度只是线性的。

Answer 3

首先将字符串转换为一组唯一字符和出现次数，例如BANANA – >（3，A），（1，B），（2，N）。 （这可以通过排序字符串和分组字母来完成）。 然后，对于集合中的每个字母，将该字母前置到集合的所有排列中，少一个字母（注意递归）。 继续“BANANA”的例子，我们有：排列（（3，A），（1，B），（2，N））= A :(排列（（2，A），（1，B），（2） ，N））++ B :(置换（（3，A），（2，N））++ N :(置换（（3，A），（1，B），（1，N））

这是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)) 

Answer 4

在我的解决方案中，我递归地生成选项，每次都尝试添加我不需要使用的每个字母。

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

使用示例：

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

Answer 5

这是一个棘手的问题，我们需要使用递归来查找字符串的所有排列，例如“AAB”排列将是“AAB”，“ABA”和“BAA”。 我们还需要使用Set来确保没有重复的值。

 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