如何生成列表的所有排列？

Question

如何生成列表的所有排列？例如：

 permutations([])
[]

permutations([1])
[1]

permutations([1, 2])
[1, 2]
[2, 1]

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

原文由 Ricardo Reyes 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

使用 标准库 中的 itertools.permutations ：

 import itertools
list(itertools.permutations([1, 2, 3]))

---

改编自 这里 是如何实现 itertools.permutations 的演示：

 def permutations(elements):
    if len(elements) <= 1:
        yield elements
        return
    for perm in permutations(elements[1:]):
        for i in range(len(elements)):
            # nb elements[0:1] works in both string and list contexts
            yield perm[:i] + elements[0:1] + perm[i:]

itertools.permutations 的文档中列出了几种替代方法。这是一个：

 def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

另一个，基于 itertools.product ：

 def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

原文由 Eli Bendersky 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

对于 Python 2.6 及 更高版本：

 import itertools
itertools.permutations([1, 2, 3])

这作为生成器返回。使用 list(permutations(xs)) 作为列表返回。

原文由 Brian 发布，翻译遵循 CC BY-SA 4.0 许可协议