有没有通用的方法阻止随意的生成重复项的功能。当然，您始终可以过滤掉重复项，但您不希望这样做，并且有充分的理由。所以你需要一个special仅生成非重复项的方法。
一种方法是按字典顺序递增生成排列。然后您可以比较“新”排列是否与上一个排列相同，然后跳过它。它变得更好：用于按字典顺序递增生成排列的算法，给出于http://en.wikipedia.org/wiki/Permutations#Generation_in_lexicography_order http://en.wikipedia.org/wiki/Permutations#Generation_in_lexicographic_order甚至根本不生成重复项！
However，这不是您问题的答案，因为它是一种不同的算法（尽管也基于交换）。
那么，让我们仔细看看你的算法。一个关键的观察结果是：
- 一旦角色交换位置
begin，它将保留在那里用于所有嵌套调用permute.
我们将把它与以下关于排列的一般观察结合起来：
- 如果你排列一个字符串
s，但仅限于有相同字符的位置，s将保持不变。事实上，所有重复排列都有不同的order对于某些字符 c 的出现，其中 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)) # use a list, as in Python strings are not mutable
现在我们通过一些记录来扩展排列函数，记录某个字符已被交换到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))
就是这样！
Almost.如果您愿意，您可以停在这里并用 C++ 重写，但如果您对某些测试数据感兴趣，请继续阅读。
我使用了稍微不同的代码进行测试，因为我不想打印所有排列。在 Python 中，您可以替换print with a yield, with 将函数转变为生成器函数，其结果可以使用 for 循环进行迭代，并且仅在需要时才计算排列。这是我使用的真实代码和测试：
def permute2(s, next_fixable, char_number, begin, end):
if end == begin + 1:
yield "".join(s) # join the characters to form a string
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，正如您所期望的那样。
