没有通用的方法可以防止任意函数生成重复项。当然，你总可以过滤掉重复项，但出于非常好的原因，你不想这样做。因此，你需要一种特殊的方法来仅生成非重复项。
一种方法是按词典顺序递增生成排列。然后你只需比较一个“新”的排列是否与上一个相同，然后跳过它即可。更好的是：在http://en.wikipedia.org/wiki/Permutations#Generation_in_lexicographic_order给出的生成排列的算法中根本不会生成重复项！
然而，这不是你问题的答案，因为它是一个不同的算法（虽然也基于交换）。
因此，让我们更仔细地看一下你的算法。一个关键观察是：
- 一旦一个字符被交换到位置
begin ，它将在所有嵌套调用 permute 中保持在那里。
我们将把这个与关于排列的以下一般性观察相结合：
- 如果你对字符串
s 进行排列，但只在相同字符的位置进行排列，那么 s 将保持不变。实际上，所有重复排列在某个字符c的出现顺序不同的位置上都有不同的顺序。
好的，所以我们所要做的就是确保每个字符的出现顺序始终与开头相同。以下为代码，但......我实际上不会C ++，因此我将使用Python，并希望它能过得去。
我们从你原来的算法开始，改写成'伪代码'：
def permute(s, begin, end):
if end == begin + 1:
print(s)
else:
for i in range(begin, end):
s[begin], s[i] = s[i], s[begin]
permute(s, begin + 1, end)
s[begin], s[i] = s[i], s[begin]
一个辅助函数，使得调用它更加容易：
def permutations_w_duplicates(s):
permute(list(s), 0, len(s))
现在我们通过一些记录来扩展排列函数，记录每个字符被交换到“begin”位置（即已经被“fixed”）的次数，并记住每个字符出现的原始顺序（char_number）。然后，我们尝试将每个要交换到“begin”位置的字符按照原始顺序依次交换，也就是说，一个字符的固定次数定义了该字符下一个可固定的原始出现次数，我称之为“next_fixable”。
def permute2(s, next_fixable, char_number, begin, end):
if end == begin + 1:
print(s)
else:
for i in range(begin, end):
if next_fixable[s[i]] == char_number[i]:
next_fixable[s[i]] += 1
char_number[begin], char_number[i] = char_number[i], char_number[begin]
s[begin], s[i] = s[i], s[begin]
permute2(s, next_fixable, char_number, begin + 1, end)
s[begin], s[i] = s[i], s[begin]
char_number[begin], char_number[i] = char_number[i], char_number[begin]
next_fixable[s[i]] -= 1
再次，我们使用一个辅助函数：
def permutations_wo_duplicates(s):
alphabet = set(s)
next_fixable = dict.fromkeys(alphabet, 0)
count = dict.fromkeys(alphabet, 0)
char_number = [0] * len(s)
for i, c in enumerate(s):
char_number[i] = count[c]
count[c] += 1
permute2(list(s), next_fixable, char_number, 0, len(s))
这就是了！
差不多了。如果您喜欢，可以在此停下并改用C++重写，但如果您对一些测试数据感兴趣，请继续阅读。
我使用了略微不同的代码进行测试，因为我不想打印所有的排列组合。在Python中，您可以将
print替换为
yield，这会使函数变成生成器函数，其结果可以用for循环迭代，并且只有在需要时才会计算排列组合。这是我使用的真实代码和测试：
def permute2(s, next_fixable, char_number, begin, end):
if end == begin + 1:
yield "".join(s)
else:
for i in range(begin, end):
if next_fixable[s[i]] == char_number[i]:
next_fixable[s[i]] += 1
char_number[begin], char_number[i] = char_number[i], char_number[begin]
s[begin], s[i] = s[i], s[begin]
for p in permute2(s, next_fixable, char_number, begin + 1, end):
yield p
s[begin], s[i] = s[i], s[begin]
char_number[begin], char_number[i] = char_number[i], char_number[begin]
next_fixable[s[i]] -= 1
def permutations_wo_duplicates(s):
alphabet = set(s)
next_fixable = dict.fromkeys(alphabet, 0)
count = dict.fromkeys(alphabet, 0)
char_number = [0] * len(s)
for i, c in enumerate(s):
char_number[i] = count[c]
count[c] += 1
for p in permute2(list(s), next_fixable, char_number, 0, len(s)):
yield p
s = "FOOQUUXFOO"
A = list(permutations_w_duplicates(s))
print("%s has %s permutations (counting duplicates)" % (s, len(A)))
print("permutations of these that are unique: %s" % len(set(A)))
B = list(permutations_wo_duplicates(s))
print("%s has %s unique permutations (directly computed)" % (s, len(B)))
print("The first 10 permutations :", A[:10])
print("The first 10 unique permutations:", B[:10])
结果是：
FOOQUUXFOO has 3628800 permutations (counting duplicates)
permutations of these that are unique: 37800
FOOQUUXFOO has 37800 unique permutations (directly computed)
The first 10 permutations : ['FOOQUUXFOO', 'FOOQUUXFOO', 'FOOQUUXOFO', 'FOOQUUXOOF', 'FOOQUUXOOF', 'FOOQUUXOFO', 'FOOQUUFXOO', 'FOOQUUFXOO', 'FOOQUUFOXO', 'FOOQUUFOOX']
The first 10 unique permutations: ['FOOQUUXFOO', 'FOOQUUXOFO', 'FOOQUUXOOF', 'FOOQUUFXOO', 'FOOQUUFOXO', 'FOOQUUFOOX', 'FOOQUUOFXO', 'FOOQUUOFOX', 'FOOQUUOXFO', 'FOOQUUOXOF']
请注意，排列顺序与原始算法相同，只是没有重复。请注意，37800 * 2！* 2！* 4！= 3628800，就像你所期望的一样。
