itertools.permutations详解 - Python排列与路径规划

一、概述

itertools.permutations 是 Python 标准库 itertools 模块中的组合迭代器之一，用于生成可迭代对象中元素的所有排列。排列是指从 n 个元素中取出 r 个元素，按照一定顺序进行排列，顺序不同则视为不同的排列。

如果不指定 r，则默认生成所有元素的全排列。排列在密码学、概率统计、路径规划、算法设计等领域有广泛应用。

二、语法

itertools.permutations(iterable, r=None)

三、参数说明

四、返回值

返回一个迭代器对象，产生所有长度为 r 的排列元组。排列按照输入可迭代对象中的元素顺序生成。结果总数为 P(n, r) = n! / (n-r)!，其中 n 为输入元素个数。

五、代码示例

示例1：全排列

import itertools

# 3个元素的全排列
perms = list(itertools.permutations([1, 2, 3]))
print("全排列:")
for p in perms:
    print(p)
print(f"总数: {len(perms)}")

# 输出：
# 全排列:
# (1, 2, 3)
# (1, 3, 2)
# (2, 1, 3)
# (2, 3, 1)
# (3, 1, 2)
# (3, 2, 1)
# 总数: 6

3 个元素的全排列有 3! = 6 种。permutations 按照字典序生成排列，保证结果的可预测性。

示例2：部分排列

import itertools

# 从4个元素中取2个排列
perms = list(itertools.permutations('ABCD', 2))
print("取2个排列:", perms)
print(f"总数: {len(perms)}")

# 输出：
# 取2个排列: [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'A'), ('B', 'C'), ('B', 'D'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'A'), ('D', 'B'), ('D', 'C')]
# 总数: 12

从 4 个元素中取 2 个排列，结果为 P(4,2) = 4! / (4-2)! = 12 种。注意 ('A', 'B') 和 ('B', 'A') 是不同的排列。

示例3：实际应用——旅行商问题

import itertools

# 旅行商问题：找出访问所有城市的最短路径
cities = ['北京', '上海', '广州', '深圳']
distances = {
    ('北京', '上海'): 1200, ('北京', '广州'): 2100, ('北京', '深圳'): 2200,
    ('上海', '广州'): 1300, ('上海', '深圳'): 1400,
    ('广州', '深圳'): 140,
}

def get_distance(a, b):
    return distances.get((a, b), distances.get((b, a), float('inf')))

# 穷举所有路径（不含起点）
best_route = None
min_dist = float('inf')
for perm in itertools.permutations(cities[1:]):
    route = [cities[0]] + list(perm)
    total = sum(get_distance(route[i], route[i+1]) for i in range(len(route)-1))
    if total < min_dist:
        min_dist = total
        best_route = route

print(f"最短路线: {' -> '.join(best_route)}")
print(f"总距离: {min_dist} km")

# 输出：
# 最短路线: 北京 -> 上海 -> 广州 -> 深圳
# 总距离: 2640 km

这是 permutations 的经典应用：旅行商问题（TSP）。通过穷举所有可能的访问顺序，找出最短路径。对于少量城市，这种方法简单有效。

六、实际应用场景

• 路径规划：穷举所有可能的访问顺序，寻找最短路径（旅行商问题）

• 密码学：生成所有可能的排列组合用于密码分析

• 赛程安排：生成所有可能的比赛对阵顺序

七、注意事项

注意1：排列数量随元素个数呈阶乘增长，P(10,10) = 3628800，P(15,15) 约为 1.3 万亿。对于较大的 n，请谨慎使用。

注意2：permutations 基于元素的位置进行排列，而非元素的值。如果输入中有重复元素，结果中也会出现"重复"的排列（它们在值上相同，但来自不同位置）。

注意3：如果 r 大于输入元素个数，则返回空迭代器。

提示：如果需要去重排列（输入有重复元素时），可以用 set() 去重：set(permutations(iterable, r))。

八、相关方法对比

九、小结

• permutations 生成所有排列，考虑顺序，不允许重复选取同一元素

• 不指定 r 时生成全排列，指定 r 时生成部分排列

• 结果数量为阶乘级增长，大数据集需谨慎

• 输入有重复元素时，结果中可能包含值相同的排列

十、练习题