以前高師大英語所碩班的同學明中昨晚來電詢問 : 如果有 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 檔了.
沒有留言 :
張貼留言