萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網頁製作 >> HTML 腳本教學

Python 標準遞歸算法實現數組全排列:生成器版與列表版

遞歸生成器版(內存高效,推薦)

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 倍+)

應用場景

  • 組合優化問題(旅行商、任務調度)
  • 測試用例生成(參數組合覆蓋)
  • 密碼暴力破解(教學演示)
  • 遊戲狀態空間搜索
copyright © 萬盛學電腦網 all rights reserved