排列列表中的重复项

Question

我正在使用 itertools 库中的 permutations 函数来打印字符串的排列列表。在这种情况下，它是 baca。但是，输出列表中的每个元素都有重复项。这是：

['aabc', 'aabc', 'aacb', 'aacb', 'abac', 'abac', 'abca', 'abca', 'acab', 'acab', 'acba', 'acba', 'baac', 'baac', 'baca', 'baca', 'bcaa', 'bcaa', 'caab', 'caab', 'caba', 'caba', 'cbaa', 'cbaa']

这是我的代码。这很简单。我在我的代码中没有看到任何会产生这种行为的东西。

from itertools import permutations

def rearrangeWord(word):
    p = [''.join(i) for i in permutations(word) ]
    print(sorted(p))

rearrangeWord('baca')

Answer 1

您正在复制所有 'aa' 个排列。

print(sorted(set(p)))

Answer 2

这解决了我的问题：

print(sorted(dict.fromkeys(p)))

现在这是输出：

['aabc', 'aacb', 'abac', 'abca', 'acab', 'acba', 'baac', 'baca', 'bcaa', 'caab', 'caba', 'cbaa']

Answer 3

multiset_permutations可以找到多个项目的排列。

>>> from sympy.utilities.iterables import multiset_permutations
>>> s = 'baca'


>>> for item in multiset_permutations(s):
    print(item)


['a', 'a', 'b', 'c']
['a', 'a', 'c', 'b']
['a', 'b', 'a', 'c']
['a', 'b', 'c', 'a']
['a', 'c', 'a', 'b']
['a', 'c', 'b', 'a']
['b', 'a', 'a', 'c']
['b', 'a', 'c', 'a']
['b', 'c', 'a', 'a']
['c', 'a', 'a', 'b']
['c', 'a', 'b', 'a']
['c', 'b', 'a', 'a']

Answer 4

如果先排序单词（这样便宜很多），就不需要再排序了：

>>> [*dict.fromkeys(map(''.join, permutations(sorted('baca'))))]
['aabc', 'aacb', 'abac', 'abca', 'acab', 'acba', 'baac', 'baca', 'bcaa', 'caab', 'caba', 'cbaa']

排列列表中的重复项

Duplicates in list of permutations

python

algorithm

permutation

itertools