如何在 Python 中生成列表的所有排列

你可以使用 Python 标准库生成列表的排列，也可以在需要自定义过程时选择递归或迭代算法。排列是对选定元素进行排序后得到的结果；与组合不同，排列中的顺序很重要。结果数量会按阶乘级增长，因此只有输入规模较小时，生成所有顺序才切实可行。

使用 itertools 库

大多数情况下，使用 itertools.permutations 即可。它会返回一个由元组组成的迭代器，因此你可以逐个处理结果，而不必立刻构造一个列表。默认情况下，r 等于输入的长度，所以每个结果都会使用所有元素。下面的示例中，r=2 表示生成有序二元组，循环则会依次处理从 1 到 3 的每种长度。

对于列表 [1, 2, 3]，程序会打印：

from itertools import permutations

data = [1, 2, 3]
print("full:", list(permutations(data)))
print("length 2:", list(permutations(data, r=2)))
print("lengths 1 to 3:")
for r in range(1, len(data) + 1):
    print(r, list(permutations(data, r)))

full: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
length 2: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
lengths 1 to 3:
1 [(1,), (2,), (3,)]
2 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
3 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

r 参数用于设置每个元组包含多少个元素。如需生成所有非空长度的排列，可以像上面那样，从 1 到输入长度逐一调用该函数。itertools.permutations 按元素所在的位置处理输入：如果同一个值在输入中出现多次，结果元组也可能重复。

有关完整的函数签名和行为，请参阅 itertools 官方文档。

使用递归函数生成排列

递归解法依次选取每个元素，再将它放到剩余元素的每种排列之前。基本情况返回一个只包含空排列的列表；这样，无论输入长度是多少（包括 0），构造过程都能成立。此实现返回列表而不是元组，适合学习或自定义排列的构造过程。

def permute(data):
    if not data:
        return [[]]

    result = []
    for index, item in enumerate(data):
        remaining = data[:index] + data[index + 1:]
        for tail in permute(remaining):
            result.append([item] + tail)
    return result

print(permute([1, 2, 3]))

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

每次递归调用都会移除一个位置上的元素，因此剩余输入会逐渐变短，直到到达基本情况。若不同位置上有相同的值，生成的列表仍可能重复。此实现会保存全部结果并进行大量递归调用，因此更适合学习或处理较小输入；如果不需要自定义构造过程，使用标准库迭代器即可。

使用迭代方法生成排列

你也可以把每个新元素插入已有的部分排列中的每个位置，以此逐步构造结果。列表最初只含一个空排列；处理到第 k 个输入元素时，排列数量会乘以 k。这种方法不需要递归调用，但仍会保存所有结果。

def iterative_permute(data):
    results = [[]]
    for item in data:
        next_results = []
        for ordering in results:
            for index in range(len(ordering) + 1):
                next_results.append(ordering[:index] + [item] + ordering[index:])
        results = next_results
    return results

print(iterative_permute([1, 2, 3]))

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

插入顺序决定该方法返回结果的先后次序，但不会改变生成的排列集合。若这种逐步构造方式适合你的任务，可以选择它；同时要考虑保存全部结果所需的内存。

总结

若想简洁地逐个获取排列，可使用 itertools.permutations，并通过 r 指定所需长度。若要自定义或学习构造过程，可以使用递归或迭代插入。长度为 n 的列表按位置计算有 n! 个完整排列，因此处理时间以及将结果全部保存时的空间需求都会迅速增长。输入较大时，可以按需处理迭代器，或只生成问题实际需要的长度和选取方式。

常见问题

1. 什么是排列？
   排列是按顺序选取的元素。例如，[1, 2] 和 [2, 1] 是不同的排列，因为它们的顺序不同。

2. itertools.permutations 如何工作？
   它会从输入可迭代对象中生成长度为 r 的元组。如果省略 r，则使用完整的输入长度。该函数会惰性地产生结果，但将迭代器转换为列表会把所有结果都保存在内存中。

3. 输入中有重复值时会怎样？
   该函数区分的是元素的位置，而不是值是否相等。因此，重复的输入值可能产生相同的元组。如果元素可哈希，将所有结果转换为集合可以在生成之后去掉重复元组，但无法避免重复结果被生成。若要避免重复计算，应使用能在每一步跳过相同选项的算法。

4. 排列有多少种？
   对于有 n 个位置的输入，按位置计算有 n! 种完整排列。如果只选取 r 个位置，排列数为 n! / (n - r)!。

5. 输入最多可以有多大？
   没有一个适用于所有机器和任务的固定上限。排列数量按阶乘级增长，即使输入规模适中，处理成本也可能很高；保存全部结果还会占用大量内存。如果不需要一次取得所有完整排列，可以优先使用惰性迭代，或减小 r。