如何生成列表的所有排列?例如:

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]

当前回答

对于性能,一个由Knuth启发的numpy解决方案(第22页):

from numpy import empty, uint8
from math import factorial

def perms(n):
    f = 1
    p = empty((2*n-1, factorial(n)), uint8)
    for i in range(n):
        p[i, :f] = i
        p[i+1:2*i+1, :f] = p[:i, :f]  # constitution de blocs
        for j in range(i):
            p[:i+1, f*(j+1):f*(j+2)] = p[j+1:j+i+2, :f]  # copie de blocs
        f = f*(i+1)
    return p[:n, :]

复制大量内存可节省时间-它比列表(itertools.permutations(range(n))快20倍:

In [1]: %timeit -n10 list(permutations(range(10)))
10 loops, best of 3: 815 ms per loop

In [2]: %timeit -n100 perms(10) 
100 loops, best of 3: 40 ms per loop

其他回答

对于Python,我们可以使用itertools并导入排列和组合来解决问题

from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))

人们确实可以对每个排列的第一个元素进行迭代,正如tzwen的答案。然而,这样编写此解决方案更有效:

def all_perms(elements):
    if len(elements) <= 1:
        yield elements  # Only permutation possible = no permutation
    else:
        # Iteration over the first element in the result permutation:
        for (index, first_elmt) in enumerate(elements):
            other_elmts = elements[:index]+elements[index+1:]
            for permutation in all_perms(other_elmts): 
                yield [first_elmt] + permutation

这个解决方案大约快了30%,显然是因为递归以len(元素)<=1而不是0结尾。它的内存效率也高得多,因为它使用了一个生成器函数(通过yield),就像Riccardo Reyes的解决方案一样。

这是受Haskell实现使用列表理解的启发:

def permutation(list):
    if len(list) == 0:
        return [[]]
    else:
        return [[x] + ys for x in list for ys in permutation(delete(list, x))]

def delete(list, item):
    lc = list[:]
    lc.remove(item)
    return lc

注意,该算法具有n个阶乘时间复杂度,其中n是输入列表的长度

打印跑步结果:

global result
result = [] 

def permutation(li):
if li == [] or li == None:
    return

if len(li) == 1:
    result.append(li[0])
    print result
    result.pop()
    return

for i in range(0,len(li)):
    result.append(li[i])
    permutation(li[:i] + li[i+1:])
    result.pop()    

例子:

permutation([1,2,3])

输出:

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

如果有人喜欢这个丑陋的单行线(虽然只适用于字符串):

def p(a):
    return a if len(a) == 1 else [[a[i], *j] for i in range(len(a)) for j in p(a[:i] + a[i + 1:])]