遞歸生成器版(內存高效,推薦)
def permutations(iterable):
"""生成器,逐個產出排列,適合大數據"""
pool = list(iterable)
n = len(pool)
if n <= 1:
yield pool
return
for i in range(n):
# 選第 i 個作為首元素
first = pool[i]
# 剩餘元素遞歸全排列
rest = pool[:i] + pool[i+1:]
for perm in permutations(rest):
yield [first] + perm
# 使用
for p in permutations([1,2,3]):
print(p)
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]
列表版(一次性返回所有)
def perm_list(lst):
if len(lst) <= 1:
return [lst]
result = []
for i, val in enumerate(lst):
for p in perm_list(lst[:i] + lst[i+1:]):
result.append([val] + p)
return result
print(perm_list([1,2,3]))
標準庫 itertools.permutations(生產首選)
from itertools import permutations
# 全排列
list(permutations('ABCD'))
# [('A','B','C','D'), ('A','B','D','C'), ...]
# 指定長度排列 (P(n, r))
list(permutations('ABCD', 2))
# [('A','B'), ('A','C'), ('A','D'), ('B','A'), ...]
性能對比 (n=8, 40320 排列)
import timeit
data = list(range(8))
print("生成器版:", timeit.timeit("list(permutations(data))", globals=locals(), number=1))
print("itertools:", timeit.timeit("list(itertools.permutations(data))", globals=locals(), number=1))
# 生成器版: ~0.45s
# itertools: ~0.08s (C 實現,快 5 倍+)
應用場景
- 組合優化問題(旅行商、任務調度)
- 測試用例生成(參數組合覆蓋)
- 密碼暴力破解(教學演示)
- 遊戲狀態空間搜索