字符串的排列：如何删除重复的排列？
这是一个打印字符串字符排列的标准函数：
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; } 它工作正常，但有一个问题，它还打印一些重复的排列，exapmle：
如果字符串是“AAB”
输出是：
AAB ABA AAB ABA BAA BAA
这也有3个重复的条目。
有没有办法防止这种情况发生？
–
谢谢
Alok Kr。
记下您之前交换过的字符：
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
标准库可满足您的需求：
#include #include #include #include using namespace std; void print_all_permutations(const string& s) { string s1 = s; sort(s1.begin(), s1.end()); do { cout << s1 << endl; } while (next_permutation(s1.begin(), s1.end())); } int main() { print_all_permutations("AAB"); }
结果：
$ ./a.out AAB ABA BAA
另一种方法可能是：
-
预先排列arrays。
-
这将确保所有重复现在都是连续的。
-
所以，我们只需要查看我们修复的前一个元素（并置换其他元素）
-
如果当前元素与之前的元素相同，则不要置换。
我会这样做：首先，我生成“组”字符（即AABBBC产生两组： (AA) and (BBB) and (C) 。
首先，我们将所有AA分布迭代到n字符上。 对于找到的每个分布，我们将BBB所有分布迭代到剩余的n-2字符（未被A占用）。 对于涉及A s和B s的这些分布中的每A ，我们将C所有分布迭代到剩余的自由字符位置上。
您可以使用std::set来确保结果的唯一性。 那就是它是C ++（因为你这样标记它）。
否则 – 手动浏览结果列表并删除重复项。
您必须保存结果并对其进行后处理，而不是像现在一样立即打印。
如果您认为这是一个需要存储所有排列以供将来使用的问题，那将非常简单。
所以你将拥有一系列置换字符串。
现在想一个新问题，这也是一个需要从数组中删除重复项的标准问题。
我希望有所帮助。
@Kumar，我想你想要的是如下：
#include #include /* print all unique permutations of some text. */ void permute(int offset, int* offsets, const char* text, int text_size) { int i; if (offset < text_size) { char c; int j; /* iterate over all possible digit offsets. */ for (i=0; i < text_size; i++) { c=text[i]; /* ignore if an offset further left points to our location or to the right, with an identical digit. This avoids duplicates. */ for (j=0; j < offset; j++) { if ((offsets[j] >= i) && (text[offsets[j]] == c)) { break; } } /* nothing found. */ if (j == offset) { /* remember current offset. */ offsets[offset]=i; /* permute remaining text. */ permute(offset+1, offsets, text, text_size); } } } else { /* print current permutation. */ for (i=0; i < text_size; i++) { fputc(text[offsets[i]], stdout); } fputc('\n', stdout); } } int main(int argc, char* argv[]) { int i, offsets[1024]; /* print permutations of all arguments. */ for (i=1; i < argc; i++) { permute(0, offsets, argv[i], strlen(argv[i])); } return 0; }
这段代码是C，根据要求，它非常快，可以满足您的需求。 当然它包含一个可能的缓冲区溢出，因为偏移缓冲区有一个固定的大小，但这只是一个例子，对吧？
编辑：有没有人试过这个？ 有更简单或更快的解决方案吗？ 令人失望的是没有人评论任何进一步的评论！
void permute(string set, string prefix = ""){ if(set.length() == 1){ cout<<"\n"<
只需将其用作置换（“单词”）;
不要在string不同位置置换相同的字符。
在Python中：
def unique_permutation(a, l, r): if l == r: print ''.join(a) return for i in range(l, r+1): if i != l and a[i] == a[l]: continue a[i], a[l] = a[l], a[i] unique_permutation(a, l+1, r) a[i], a[l] = a[l], a[i]
算法步骤：
- 将给定的字符串存储到临时字符串中，例如“temp”
- 从临时字符串中删除重复项
- 最后调用“void permute（char * a，int i，int n）”函数来打印给定字符串的所有排列而不重复
我认为，这是最好，最有效的解决方案。