如何在Python中生成列表的所有排列，而与列表中元素的类型无关？

例如：

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 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

从Python 2.6开始(如果我们使用的是Python 3)，我们可以使用一个标准库工具：itertools.permutations。

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

如果我们出于某种原因使用旧版Python(<2.6)，或者只是想知道它的工作原理，那么这是一种不错的方法，该方法取自http://code.activestate.com/recipes/252178/：

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(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)

在Python 2.6及更高版本中：

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

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

原谅我的python文盲，因为我不会在python中提供解决方案。
由于我不知道python 2.6使用哪种方法来生成排列，而eliben的方法看起来像Johnson-Trotter排列生成，因此我们可能会寻找文章
在Wikipedia上的Permutations及其生成中，看起来很像Myrvold和Ruskey在论文中提出的非排序功能。

在我看来，这可以与其他答复中所述的方式在生成器中使用，以大大减少内存需求。请记住，排列不会按字典顺序排列。

以下代码是给定列表的就地排列，实现为生成器。由于仅返回对列表的引用，因此不应在生成器外部修改列表。
解决方案是非递归的，因此使用低内存。输入列表中的元素的多个副本也可以很好地工作。

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

以下代码仅适用于Python 2.6及更高版本

首先，导入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)]