如何使用生成器在Python中生成没有“反向重复”的列表排列

一尘不染

algorithm

这与问题有关如何在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的生成器。

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

阅读 204

2020-07-28

共1个答案

一尘不染

我对SilentGhost的提案进行了出色的跟进-发布单独的答案，因为注释的边距太窄而无法包含代码:-)

itertools.permutations内置（自2.6版开始）且速度很快。我们只需要一个过滤条件，对于每个条件（perm，perm
[::-1]）都将接受其中的一个。由于OP表示项目始终是不同的，因此我们可以比较任意两个元素：

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

打印：

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

之所以有效，是因为反转排列总是会翻转关系！
p[0] < p[1]或任何其他对也可以，因此您还可以控制获得的排列的一半。

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

但是我怀疑（没有检查）带有2：1过滤的内置迭代器是否会胜过任何自定义实现。当然，它以简单性取胜！

2020-07-28