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

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

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)

- eliben

---

如果排列的列表足够大，这种递归解决方案和其他递归解决方案存在潜在的危险，可能会消耗所有的 RAM。 - Boris Gorelik

对于大型列表，它们也会达到递归限制（并停止运行）。 - dbr

使用生成器，所以函数本身不会占用内存。你需要决定如何消耗 all_perms 返回的迭代器（例如，你可以将每个迭代写入磁盘而不担心内存）。我知道这篇文章很旧，但我为了所有现在阅读它的人而写下这篇回答。现在最好的方法是使用 itertools.permutations()，正如许多人指出的那样。 - Jagtesh Chadha

不仅仅是一个生成器。它使用了嵌套的生成器，每个生成器向调用栈中的前一个生成器产生结果。如果不清楚的话，可以这样理解。它使用O(n)的内存，这是很好的。 - cdunn2001

我已经修复了它，使用for i in range(len(elements))代替for i in range(len(elements)+1)。实际上，被单独选出的元素elements[0:1]可以在结果中出现len(elements)次，而不是len(elements)+1次。 - Eric O. Lebigot

Answer 2

从 Python 2.6 开始:

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

这将返回一个生成器。使用list(permutations(xs))可以将其转换为列表。

- Brian

---

注意这里有一个 r 参数，例如 itertools.permutations([1,2,3], r=2)，将生成选取 2 个元素的所有可能排列：[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]。 - toto_tico

Answer 3

首先，导入itertools：

import itertools

排列（顺序有关）：

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

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

组合（顺序无关）：

print(list(itertools.combinations('123', 2)))

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

笛卡尔积（多个可迭代对象）：

print(list(itertools.product([1,2,3], [4,5,6])))

[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]

笛卡尔积（使用一个可迭代对象与自身）：

print(list(itertools.product([1,2], repeat=3)))

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

- e-satis

---

+1！文档链接：http://docs.python.org/2/library/itertools.html#itertools.permutations - Pramod

Answer 4

def permutations(head, tail=''):
    if len(head) == 0:
        print(tail)
    else:
        for i in range(len(head)):
            permutations(head[:i] + head[i+1:], tail + head[i])

被称为：

permutations('abc')

- kx2k

---

为什么要打印tail然后返回None？为什么不直接返回tail？为什么不管怎样都不返回任何东西？ - bugmenot123

@bugmenot123，你可能想要所有的最终尾部而不仅仅是尾部，这可以通过在函数中添加perms=[]参数来轻松完成，在每个print上附加它，并有一个最终的return perms。 - Alex Moore-Niemi

Answer 5

#!/usr/bin/env python

def perm(a, k=0):
   if k == len(a):
      print a
   else:
      for i in xrange(k, len(a)):
         a[k], a[i] = a[i] ,a[k]
         perm(a, k+1)
         a[k], a[i] = a[i], a[k]

perm([1,2,3])

输出：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

因为我在交换列表内容时需要可变序列类型作为输入。例如，perm(list("ball"))可以工作，而perm("ball")则不行，因为您无法更改字符串。

这个Python实现受到了Horowitz、Sahni和Rajasekeran的书《计算机算法》中所介绍的算法的启发。

- Silveira Neto

---

我假设k是排列的长度。当k = 2时，输出为[1, 2, 3]。难道不应该是(1, 2)、(1, 3)、(2, 1)、(2, 3)、(3, 1)、(3, 2)吗？ - Konstantinos Monachopoulos

k 是您想要交换的元素的索引。 - sf8193

NameError: 名称 'xrange' 未定义 - Pathros

7年后，我如何返回所有排列列表的列表？此外，这可以迭代完成吗？ - mLstudent33

这很容易通过在函数中添加perms=[]参数，每次打印时将其附加到它上面，并最终返回perms来完成。 - Aditya

Answer 6

这个解决方案实现了一个生成器，以避免将所有排列都保存在内存中：

def permutations (orig_list):
    if not isinstance(orig_list, list):
        orig_list = list(orig_list)

    yield orig_list

    if len(orig_list) == 1:
        return

    for n in sorted(orig_list):
        new_list = orig_list[:]
        pos = new_list.index(n)
        del(new_list[pos])
        new_list.insert(0, n)
        for resto in permutations(new_list[1:]):
            if new_list[:1] + resto <> orig_list:
                yield new_list[:1] + resto

- Ricardo Reyes

Answer 7

在功能式编程风格中。

def addperm(x,l):
    return [ l[0:i] + [x] + l[i:]  for i in range(len(l)+1) ]

def perm(l):
    if len(l) == 0:
        return [[]]
    return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]

print perm([ i for i in range(3)])

结果：

[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]

- Paolo

Answer 8

普通实现（无yield-将在内存中完成所有操作）：

def getPermutations(array):
    if len(array) == 1:
        return [array]
    permutations = []
    for i in range(len(array)): 
        # get all perm's of subarray w/o current item
        perms = getPermutations(array[:i] + array[i+1:])  
        for p in perms:
            permutations.append([array[i], *p])
    return permutations

产量实现：

def getPermutations(array):
    if len(array) == 1:
        yield array
    else:
        for i in range(len(array)):
            perms = getPermutations(array[:i] + array[i+1:])
            for p in perms:
                yield [array[i], *p]

基本想法是对于第一个位置遍历数组中的所有元素，然后在第二个位置上遍历除了第一个选择的元素之外的所有其他元素，以此类推。您可以使用递归来做到这一点，其中停止条件是到达一个只有1个元素的数组 - 在这种情况下，您将返回该数组。

- Maverick Meerkat

---

这个对我不起作用 _> ValueError: operands could not be broadcast together with shapes (0,) (2,) ，针对这行代码：perms = getPermutations(array[:i] + array[i+1:])。 - RK1

@RK1 输入是什么？ - Maverick Meerkat

我传入了一个 numpy 数组 _> getPermutations(np.array([1, 2, 3]))，我发现它对于列表有效，只是因为函数参数是 array 而感到困惑 :) - RK1

@RK1 很高兴它能正常工作 :-) list 是 Python 中的关键字，因此将参数命名为关键字通常不是一个好主意，因为它会“遮蔽”它。所以我使用单词数组，因为这是我正在使用的列表的实际功能 - 它们类似于数组的方式。我想如果我写文档，我会澄清这一点。此外，我认为基本的“面试”问题应该在没有外部包（如numpy）的情况下解决。 - Maverick Meerkat

@dgundersen 是的，在那里它是至关重要的。冒号需要用于解包数组。否则，您将得到一个非常混乱的结果（一个数组的数组的数组...）。 - Maverick Meerkat

Answer 9

我认为一个相当明显的方法也可能是：

def permutList(l):
    if not l:
            return [[]]
    res = []
    for e in l:
            temp = l[:]
            temp.remove(e)
            res.extend([[e] + r for r in permutList(temp)])

    return res

- tzwenn

Answer 10

以下代码是给定列表的原地置换，实现为生成器。由于它只返回对列表的引用，因此不应在生成器外修改列表。 该解决方案是非递归的，因此使用内存较低。也适用于输入列表中有多个元素副本的情况。

def permute_in_place(a):
    a.sort()
    yield list(a)

    if len(a) <= 1:
        return

    first = 0
    last = len(a)
    while 1:
        i = last - 1

        while 1:
            i = i - 1
            if a[i] < a[i+1]:
                j = last - 1
                while not (a[i] < a[j]):
                    j = j - 1
                a[i], a[j] = a[j], a[i] # swap the values
                r = a[i+1:last]
                r.reverse()
                a[i+1:last] = r
                yield list(a)
                break
            if i == first:
                a.reverse()
                return

if __name__ == '__main__':
    for n in range(5):
        for a in permute_in_place(range(1, n+1)):
            print a
        print

    for a in permute_in_place([0, 0, 1, 1, 1]):
        print a
    print

- Ber