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

Question

如何生成符合以下条件的所有排列:如果两个排列彼此相反(即[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

如果按字典顺序生成排列,那么您不需要存储任何内容来确定是否已经看到给定排列的反转.您只需按字典顺序将其与其反向进行比较 - 如果它较小则返回它,如果它更大则跳过它.

可能有一种更有效的方法,但这很简单,并且具有您需要的属性(可作为生成器实现,使用O(n)工作内存).

Answer 2

我对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)

这是有效的,因为反转排列总会翻转关系!
p[0] < p[1]或任何其他对也可以工作,所以你也可以控制你得到的一半排列.

我不确定是否有更有效的过滤方法. itertools.permutations保证字典顺序,但词典位置p和p[::-1]相关的复杂方式.特别是,只是停在中间不起作用.

但我怀疑(没有检查)具有2:1过滤的内置迭代器将胜过任何自定义实现.当然,它赢得了简单!