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

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]

当前回答

在我看来,一个很明显的方式可能是:

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

其他回答

这里有一个算法,它在不创建新的中间列表的情况下处理列表,类似于Ber在https://stackoverflow.com/a/108651/184528.

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p        
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p        
            xs[low], xs[i] = xs[i], xs[low]

for p in permute([1, 2, 3, 4]):
    print p

您可以在这里亲自尝试代码:http://repl.it/J9v

人们确实可以对每个排列的第一个元素进行迭代,正如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的解决方案一样。

此解决方案实现了一个生成器,以避免在内存中保留所有排列:

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

如果不想使用内置方法,例如:

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

你可以自己实现permute函数

from collections.abc import Iterable


def permute(iterable: Iterable[str]) -> set[str]:
    perms = set()

    if len(iterable) == 1:
        return {*iterable}

    for index, char in enumerate(iterable):
        perms.update([char + perm for perm in permute(iterable[:index] + iterable[index + 1:])])

    return perms


if __name__ == '__main__':
    print(permute('abc'))
    # {'bca', 'abc', 'cab', 'acb', 'cba', 'bac'}
    print(permute(['1', '2', '3']))
    # {'123', '312', '132', '321', '213', '231'}

我看到在这些递归函数中进行了很多迭代,而不是纯粹的递归。。。

所以对于那些连一个循环都不能遵守的人来说,这里有一个粗略的、完全不必要的完全递归的解决方案

def all_insert(x, e, i=0):
    return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else []

def for_each(X, e):
    return all_insert(X[0], e) + for_each(X[1:],e) if X else []

def permute(x):
    return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])


perms = permute([1,2,3])