經過前幾天的演算法,都需要小動腦和邏輯上的思考對吧?透過一些比較和分配的技巧,來做資料的排序。
今天,就來講講列舉法 (俗稱暴力破解法)。
列舉法 (Enumeration) 的想法非常的簡單,就是把所有可能都列出來就對啦!!!其中至少會有一組符合我們條件的答案。
舉例來說我們有一筆資料[1, 2, 3]
,並且想要知道所有的排列組合,我們只能從頭開始排列起,一一地將所有位置都列舉出來。
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
大概了解列舉法之後,這邊還有一個常見的例子。
[1, 2, 3, 4, 5, 6, 7, 8, 9]
將數字 1 到 9 填入上面的方程式,使之為 1 。
當然,第二個方程式是不成立的,所以這種時候就是使用 試誤法(Try and Error) 和 列舉 來找出所有的可能,並一一試驗看符不符合方程式。
from copy import copy
list_1to9=[1,2,3,4,5,6,7,8,9]
#在b層建一個新的1-9,然後pop掉取過的,C層再複製b取過的,建一個新的1-9,pop調取過的
#d層再複製c層取過的,建新的1-9.....以下同上。這樣就最後一行就不用再把取過的加回去了。
# 如果再稍稍修改,效率會再更好喔
for a in list_1to9: # a從list_1to9取數字
list_a=copy(list_1to9) # list_a複製list_1to9
list_a.remove(a) # 將a選取的數字從list_a去除,留下可以繼續被選取的字給b
for b in list_a: # b從list_a取數字
list_b=copy(list_a) # list_b複製list_a
list_b.remove(b) # 將b選取的數字從list_b去除,留下可以繼續被選取的字給c
for c in list_b:
list_c=copy(list_b)
list_c.remove(c)
for d in list_c:
list_d=copy(list_c)
list_d.remove(d)
for e in list_d:
list_e=copy(list_d)
list_e.remove(e)
for f in list_e:
list_f=copy(list_e)
list_f.remove(f)
for g in list_f:
list_g=copy(list_f)
list_g.remove(g)
for h in list_g:
list_h=copy(list_g)
list_h.remove(h)
for i in list_h:
#這時候選取完所有的數字,並填入方程式進行驗證,如果為是,輸出結果;如果為否,則沿著迴圈h到迴圈a一一測試各種可能。
if (a/(b*10.+c)+d/(e*10.+f)+g/(h*10.+i))==1:
print (a,b,c,d,e,f,g,h,i)
這次的程式碼是真的需要多花點時間思考,但如果用筆寫下來,會更清楚喔。
其實在資料量不大的時候,有時候也是可以偷偷用列舉法來找出所有可能,畢竟是電腦在算。而且你那小腦袋要裝的是 吃喝玩樂 更重要的演算法才對啊哈哈哈哈