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

Question

这个内容和问题 如何在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

这是一个更简洁、更快速的版本，灵感来自于ChristopheD的被接受的回答，我非常喜欢。递归真是太棒了。我让这个方法在处理输入列表时去掉了重复的项，以确保每个项都是独一无二的，不过也许它应该直接抛出一个异常来处理这种情况。

def fac(x): 
    return (1 if x==0 else x * fac(x-1))

def permz(plist):
    plist = sorted(set(plist))
    plen = len(plist)
    limit = fac(plen) / 2
    counter = 0
    if plen==1:
        yield plist
    else:
        for perm in permz(plist[1:]):
            for i in xrange(plen):
                if counter == limit:
                     raise StopIteration
                counter += 1
                yield perm[:i] + plist[0:1] + perm[i:]

# ---- testing ----
plists = [
    list('love'),
    range(5),
    [1,4,2,3,9],
    ['a',2,2.1],
    range(8)]               

for plist in plists:
    perms = list(permz(plist))
    print plist, True in [(list(reversed(i)) in foo) for i in perms]

Answer 2

如果你按照字典顺序生成排列，那么你就不需要存储任何东西来判断一个给定的排列的反向排列是否已经出现过。你只需要把它和它的反向排列进行字典顺序的比较——如果它更小，就返回这个排列；如果它更大，就跳过它。

可能还有更高效的方法，但这个方法简单，并且满足你需要的特性（可以作为生成器实现，使用的内存是O(n)）。

Answer 3

我有一个很棒的补充，关于SilentGhost的提议 - 我单独发个答案，因为评论的空间太小，放不下代码 :-)

itertools.permutations 是内置的（从2.6版本开始）而且速度很快。我们只需要一个过滤条件，确保对于每一对（perm, perm[::-1]），只接受其中一个。因为提问者说每个项目都是不同的，我们可以简单地比较任意两个元素：

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] 可以用，但其实不行 - 反转后会选到不同的元素。）

你也可以直接比较整个排列和它的反转：

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

我不太确定有没有更有效的过滤方法。itertools.permutations 保证了字典顺序，但 p 和 p[::-1] 的字典位置之间的关系比较复杂。特别是，仅仅停在中间是不够的。

不过我怀疑（没去验证）内置的迭代器加上2:1的过滤会比任何自定义实现更快。而且它在简单性上也胜出！