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

Question

查找字符串的所有排列是通过众所周知的Steinhaus-Johnson-Trotter算法.但如果字符串包含重复的字符,如
AABB,
那么可能的唯一组合将是4!/(2!*2!)= 6

实现这一目标的一种方法是我们可以将它存储在数组中,然后删除重复项.

有没有更简单的方法来修改约翰逊算法,因此我们永远不会生成重复的排列.(以最有效的方式)

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

首先将字符串转换为一组唯一字符和出现次数，例如 BANANA -> (3, A),(1,B),(2,N)。（这可以通过对字符串进行排序和对字母进行分组来完成）。然后，对于集合中的每个字母，将该字母添加到集合的所有排列中，并少一个该字母（注意递归）。继续“香蕉”的例子，我们有： permutations((3,A),(1,B),(2,N)) = A:(permutations((2,A),(1,B),(2) ,N)) ++ B:(permutations((3,A),(2,N)) ++ N:(permutations((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 3

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

#include <string.h>

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 <stdio.h>
#include <string.h>

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