优美的算法：输出给定含重复字符的串的所有可能的排列

输出一个字符串所有排列。注意有重复字符。

之前写过一个不含重复字符的串的所有排列算法。几经周折，未能想出处理重复的字符的方法。今天发愿研究了半晚上，仍然没能得出正确的解法。最终在stackoverflow上找到一个目前看到的最完美的解法。

 

该解法可作为很多排列组合组合题目的范本，以处理重复元素的情况。根据该范本，对之前的写的算法做了改进，正确处理了重复元素。

http://blog.chinaunix.net/uid-26456800-id-3444921.html

 

该算法是基于交换的，对于定的一个串，枚举出所有的两两交换的组合，即可得到所有可能的排列。

这里可以通过回溯来解决。对于一个字符来说，它只和它及它之后的字符交换。

例如abc

可能的交换有组合有

abc: 0<-->0 1<-->1 2<-->2
acb: 0<-->0 1<-->2
bac: 0<-->1 2<-->2
bca: 0<-->1 1<-->2
cab: 0<-->2 1<-->2
cba: 0<-->2 1<-->1

这里可以通过回溯来解决。对于一个字符来说，它只和它及它之后的字符交换。

 

算法的关键在于对重复字符的处理。

引入一个字符数组，用来标记与当前位置的字符交换过的字符

考虑输入abb

1.对于第一个字符a,来说，他可能的交换是自己，第一个b,第二个b

2.显然，在和第一个b交换后，和第二个b就没有必要交换了。否则会产生重复

3.更进一步，如果只还有重复的b，都无需交换。这个判定和与之交换的字符下标无关，仅和其值有关。若输入为abbcb,那么显然，a和第二个b,第三b都无交换的必要。

4.因此，可以通过一个数组，记录下当前，已经与当前处理的位置交换的过的字符。

 

a.'a'和'a'交换 --->记录record['a'] = 1;

b.'a'和'b'交换 --->记录record['b'] = 1;

c.'a'和'b'交换 --->record['b']已经为1,说明交换过，跳过

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *a, int i, int n)
{
    char was[256];
    bzero(was, 256);
        int j;
        if (i == n)
             printf("%s\n", a);

    for (j = i; j <= n; j++)
    {
        if (!was[*(a+j)]) {
            swap((a+i), (a+j));
            permute(a, i+1, n);
            swap((a+i), (a+j)); //backtrack
            was[*(a+j)] = 1;
        }
    }

}

int main(){
        char input[] = "aabbcc";
    permute(input,0,strlen(input)-1 );
}