这是一个打印字符串字符排列的标准函数:
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j < n; j++) //check till end of string
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}
void swap (char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
它工作正常但有一个问题,它还打印了一些重复的排列,例如:
如果字符串是“AAB”
输出是:
AAB
ABA
AAB
ABA
BAA
BAA
这也有 3 个重复条目。
有什么办法可以防止这种情况发生吗?
--
谢谢
阿洛克克尔
最佳答案
记下您之前交换了哪些字符:
char was[256];
/*
for(j = 0; j <= 255; j++)
was[j] = 0;
*/
bzero(was, 256);
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;
}
}
这必须是迄今为止条目中最快的一个,一些关于“AAAABBBCCD”(100 个循环)的基准:
native C - real 0m0.547s
STL next_permutation - real 0m2.141s
关于c++ - 字符串字母的排列 : How to remove repeated permutations?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6917832/