字符串排列组合问题(二)

去掉重复的全排列
上述代码有个缺陷，就是会造成重复数据的输出，例如abb这种字符串，上述程序跑完结果如图：

由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不同，则需要交换，得到bba。由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。

换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！

这样，我们得到在全排列中去掉重复的规则：
去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字交换。

贴出上面ac代码的去重版本：

[cpp] #include
#include
#include

struct seq
{
char str[7];
};

struct seq seqs[721];
int count;

int is_swap(char *str, int begin, int k)
{
int i, flag;

for (i = begin, flag = 1; i < k; i ++) {
if (str[i] == str[k]) {
flag = 0;
break;
}
}

return flag;
}

void swap(char *str, int a, int b)
{
char temp;
temp = str[a];
str[a] = str[b];
str[b] = temp;
}

void permutation_process(char *name, int begin, int end) {
int k;

if (begin == end - 1) {
strcpy(seqs[count].str, name);
count ++;
}else {
for (k = begin; k < end; k ++) {
if (is_swap(name, begin, k)) {
swap(name, k, begin);
permutation_process(name, begin + 1, end);
swap(name, k, begin);
}
}
}
}

int compare(const void *p, const void *q)
{
const char *a = p;
const char *b = q;
return strcmp(a, b);
}

int main()
{
char name[7];
int i, len;

while (scanf("%s", name) != EOF) {
count = 0;
len = strlen(name);
permutation_process(name, 0, len);
qsort(seqs, count, sizeof(seqs[0]), compare);

for (i = 0; i < count; i ++) {
printf("%s\n", seqs[i].str);
}
printf("\n");
}

return 0;
}