2023年4月17日 星期一

Python 學習筆記 : 用 itertools.permutations() 排列字集

以前高師大英語所碩班的同學明中昨晚來電詢問 : 如果有 1500 個字的英文字集每次挑 12 個字出來排列會有多少種不同的排列? 電腦的算力能否處理? 關於第一個問題, Python 的內建模組 math 內有一個 perm() 函式可輕易計算出來 (> v3.8) : 

Python 3.11.2 (C:\Users\User\AppData\Local\Programs\Python\Python311\python.exe)
>>> import math   
>>> math.perm(1500, 12)     
124147257394529035596269620244764800000
>>> print("%e" %math.perm(1500, 12))       # 用科學表示法呈現
1.241473e+38

哇, 是 38 次方等級的龐然大物, 不知 PC 能否扛得起哩. 不過還會加上一些限制條件, 或許不會到這麼龐大啦 (其實還是很大), 參考 :


此處摘要一下數學中排列 (permutation) 與組合 (combination) 的差別, 排列與順序有關, 組合則與順序無關, 元素一樣但順序不一樣算不同的排列, 但卻是同一種組合, 例如 a, b, c 三個字元每次挑兩個, 有 ab, ba, ac, ca, bc, cb 六種排列, 但卻只有 ab, ac, bc 三種組合 (因為 ab/ba, ac/ca, bc/cb 都各算一種組合), 其數學公式如下 : 



雖然可以用 math.factorial() 函式根據上面的算式來計算排列組合數, 但在 Python 3.8 版後 math 模組新增了 perm()comb() 函式, 可用來分別計算排列數與組合數, 不需要自行套公式來算, 參考 :


組合數因為與順序無關會比排列數來得少, 1500 取 12 結果是 29 次方等級 :

>>> math.comb(1500, 12)   
259179212333589356687471649875   
>>> print("%e" %math.comb(1500, 12))    
2.591792e+29

在 1500 個字集準備好之前, 我先用 A~Z 這 26 個字母做個簡單測試, 作法是利用 Python 標準函式庫 itertools 中的 permutations() 函式來列出所有排列, 參考 : 


itertools.permutations() 函式可傳入兩個參數 : 


第一個參數為可迭代物件 (必要參數), 第二個參數 (備選參數) 是傳回值的排列長度 (即選幾個來排列), 例如從 26 個英文字母中取 5 個來排列 : 

>>> import math  
>>> from itertools import permutations     
>>> letters=list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')     
>>> letters   
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
>>> math.perm(26, 5)      # 26 取 5 有近 79 萬種排列方式
7893600
>>> for p in permutations(letters, 5): 
    print(p)                          # 會印很久
    
將近 79 萬種排列在互動環境就跑了好久啊! 真不敢想像那 38 次方會怎樣! 不過, 在互動環境 print 結果本來就慢很多, 我將上面的指令加上計時功能寫成如下程式檔案, 並將排列結果輸出到檔案, 在 Thonny 中執行就快多了, 也才用了 30 秒不到 : 

# perm_test.py
import time
import math
from itertools import permutations

start=time.time()
letters=list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
f=open('permutation.csv', 'w')
for p in permutations(letters, 5):
    f.write(','.join(p) + '\n')
f.close()
end=time.time()
print(f'time elapsed : {end-start}')

>>> %Run perm_test.py
time elapsed : 27.593969345092773   

結果得到一個大小約 84MB 的 csv 檔, 節錄內容頭尾如下 :


.......


雖然看來很快, 但還無法估算 38 次方要跑多久才跑得完, 以及檔案有多大. 


2023-04-20 補充 :

昨天收到測試用的 238 字字集, 存在 A~Z 欄的 Excel 檔案裡, 我將其另存成 CSV 檔 : 




其中連續的逗號來自空格, 清除換列字元與空格後, 實際字數為 238 字. 如果從 238 個字中挑選 12 個, 其排列數計算如下 :

>>> import math   
>>> math.perm(238, 12)    
24917297304498261278500684800
>>> print("%e" %math.perm(238, 12))    
2.491730e+28

哇, 是 18 次方等級的. 

接著寫了如下之程式來處理 (238, 12) 的排列情況 :

# words_permutation.py
import time
import math
from itertools import permutations

start=time.time()
with open('TW_seed_phrase_test.csv', 'r', encoding='utf8') as f:
    lines=f.readlines()
words_str=','.join(lines)
words_str=words_str.replace('\n', '')
words_list=words_str.split(',')
words_list=list(filter(lambda word: word != '', words_list))
words_list.sort()
with open('words_permutation.csv', 'w', encoding='utf8') as f:
    for p in permutations(words_list, 12):
        f.write(' '.join(p) + '\n')
print(words_list)
print(len(words_list))
end=time.time()
print(f'time elapsed : {end-start}')

此處先用字串的 split() 方法以逗號為界將字串 words_str 拆成串列, 但 EXCEL 中的空格會在匯出為 CSV 檔時產生連續逗號, 拆解時會在串列中變成空字串, 這裡利用了內建函式 filter() 來清除這些空字串, 它的傳入參數是一個傳回 True/Fasle 的函式 (辨認可迭代物件之元素是否為空字串), filter() 會將傳回 True 的可迭代物件元素傳回, 參考 : 


然後將請裡過的 words_list 串列丟給 math.permutations() 去做排列, 它會傳回一個 generator, 只要迭代此 generator 就可以產生各個排列結果 (tuple), 將此 tuple 以空格隔開組成字串後寫入輸出檔案即可. 關於檔案讀寫參考 :


跑了 5 個多小時還沒結束 ...... 持續觀察中. 

跑了快 6 小時發現程式因為 "maximum recursion depth exceeded" (超過最大迭代深度) 跳離, 同時 400 多 GB 的硬碟也快用光了 : 

Python 3.11.2 (C:\Users\User\AppData\Local\Programs\Python\Python311\python.exe)
>>> object address  : 00000229B953BDC0
object refcount : 2
object type     : 00007FF838D13550
object type name: RecursionError 
object repr     : RecursionError('maximum recursion depth exceeded')
lost sys.stderr

Process ended with exit code 1.

檢視輸出檔真的來到 424GB 左右 : 




用 EXCEL 開啟時會詢問 CSV 的區隔字元, 可看出輸出結果正確, 只是檔案太大開了好久都沒開起來只好放棄 : 




看樣子必須想辦法切割輸出的 CSV 檔了.

沒有留言 :