防止重复的itertools.permutations

Question

我想得到使用2A和2B的4个字符串的所有唯一排列

from itertools import permutations

perm = permutations('AABB', 4)
for i in list(perm):
    print(i)

这让我感觉到

('A', 'A', 'B', 'B')
('A', 'A', 'B', 'B')
('A', 'B', 'A', 'B')
('A', 'B', 'B', 'A')
...

如你所见，我得到了复制件。我想这是因为它把A放在第一位和第二位是不同的值，但是对我来说，AABB只是一个唯一的结果。

我可以通过把所有的结果都放到一个集合中来解决这个问题，但是我认为我只是用错了置换函数。

如何使用置换函数得到所有唯一的排列使用2A‘s和2B’s没有得到的陷阱？

Answer 1

在迭代工具中没有直接的方法可以做到这一点。permutations()的文档声明：

根据元素的位置而不是它们的价值，元素被视为独一无二的元素。

这意味着，尽管这两个A看起来与您相等，但迭代工具将它们视为不相等，因为它们在原始字符串中有不同的位置。

您想要的结果的数目称为4个值的多项式系数，2个相等，另2个相等。您可以通过将自己的等效函数编码为permutations来获得所需的东西，但这需要一段时间才能编写代码和调试。(虽然这个词指的是一个数字，而不是实际的列表，但它可能被称为multinomial。)一种更简单的方法，也许在执行和内存使用方面较慢，但在编程中却要快得多，那就是使用permutations和Python的set来删除重复的。你可以这样做：

from itertools import permutations

perm = permutations('AABB', 4)
for i in set(perm):
    print(i)

这可能会导致与打印输出不同的顺序。如果希望恢复原始顺序，请使用sorted(set(perm))，因为permutations按字典顺序返回(如果原始字符串按排序顺序排列)。

Answer 2

您可以在set上迭代或使用hashing

from itertools import permutations, combinations

perm = set(permutations('AABB', 4))
for i in <b>perm</b>:
    print(i)

#Output
('A', 'A', 'B', 'B')
('A', 'B', 'A', 'B')
('A', 'B', 'B', 'A')
('B', 'A', 'A', 'B')
('B', 'B', 'A', 'A')
('B', 'A', 'B', 'A')  

使用字典：

from itertools import permutations, combinations
dicta = {}
perm = permutations('AABB', 4)
for i in list(perm):
    if i in dicta:
        dicta[i] += 1
    else:
        dicta[i] = 1
print([i for i in dicta.keys()])

Answer 3

您应该使用more_itertools.distinct_permutations来实现这一点。

from more_itertools import distinct_permutations as idp
for p in idp('ABB'):
    print(p)