python - 如何使用生成器在 Python 中生成不带 "reverse duplicates"的列表排列

Question

这与问题 How to generate all permutations of a list in Python 有关

如何生成符合以下条件的所有排列:如果两个排列彼此相反(即 [1,2,3,4] 和 [4,3,2, 1]), 它们被认为是相等的，只有其中一个应该在最终结果中。

例子:

permutations_without_duplicates ([1,2,3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]

我正在排列包含唯一整数的列表。

生成的排列数量会很高，所以我想尽可能使用 Python 的生成器。

编辑:如果可能的话，我不想将所有排列的列表存储到内存中。

Answer 1

我对 SilentGhost 的提议进行了精彩的跟进 - 发布一个单独的答案，因为评论的边距太窄而无法包含代码:-)

itertools.permutations内置(自 2.6 起)且速度快。我们只需要一个过滤条件，对于每个 (perm, perm[::-1]) 都会接受其中一个。由于 OP 说项目总是不同的，我们可以只比较任何 2 个元素:

for p in itertools.permutations(range(3)):
    if p[0] <= p[-1]:
        print(p)

打印:

(0, 1, 2)
(0, 2, 1)
(1, 0, 2)

这是有效的，因为反转排列总是会翻转第一个和最后一个元素之间的关系!

对于 4 个或更多元素，围绕中间对称的其他元素对(例如每边第二个 p[1] <= p[::-1][1])也可以。
(这个答案之前声称 p[0] < p[1] 会起作用，但它不会——在 p 被反转后，它会选择不同的元素。)

您还可以对整个排列与反向排列进行直接字典序比较:

for p in itertools.permutations(range(3)):
    if p <= p[::-1]:
        print(p)

我不确定是否有更有效的过滤方法。 itertools.permutations保证字典顺序，但字典位置p和 p[::-1]以相当复杂的方式相关。特别是，仅仅停在中间是行不通的。

但我怀疑(未检查)具有 2:1 过滤的内置迭代器会优于任何自定义实现。当然，它以简单取胜!