發表文章

目前顯示的是 1月, 2014的文章

快速組合算法(Fast Combination Algorithm)

在 猜數字遊戲 (電腦猜人) 這篇文章裡,最後提到怎麼從10個數字裡面挑出4個數字的組合的方法。 這個方法很簡單,0x3ff這個數字共有10個位元1(bit),我們可以把這10個位元和0-9這10個數字作一一對應。用一個迴圈來找從1到0x3ff這些數字裡面,有那些數字是包含4個位元1,也就是要找的。例如0xf這個數字,2進制是0000 0000 0000 1111,最右邊4個bit都是1,根據1的位置轉換後變成3210這個數字。同理0x17這個數,2進制是0000 0000 0001 0111也是4個bits為1,轉換後為4210這個數字。依此類推。 這個方法用來選取小範圍數的組合還可以,可是一但數字大了,效能就太慘不忍睹了。例如以今彩539的可能組合為例,全部1-39共39個數字裡面挑出5個,全部共有575757種組合。雖然57萬多種組合看起來不大,但是以上面的方法來找,則要搜尋的迴圈範圍一下暴漲為2^39才能得到這57萬組結果,這是一個天文數字。所以這個方法就不可行了,勢必要使用更有效率的演算法才行。 稍微研究後,很幸運的不到10鐘就讓我找到了一個看來可行的演算法,很快的寫了一支小程式來測試。測試結果果然很理想,以C(39,5)作計算測試,不到1秒鐘的時間就得到正確結果! ; 底下是演算法的概述,同樣以10個數字取組合為例: * 考慮最簡單的情況,作10取1組合 0 1 2 3 4 5 6 7 8 9 10個數字共有10個位置可以放入數字1,從最左邊的位置開始,共有10個位置可選擇,所以總共有10種可能。 用計算組合的公式驗算一下,C(10,1)=10!/1!(10-1)!=10!/1!9!=10 * 考慮10取2的情形 因為第一個1有0-9共10個位置可以選擇,如果第一個1選擇放入位置0,則第二個1有1-9共9種位置可以選擇放入。因為位置0的情況已經考慮過,所以接下來只要往後看不再往前看,需要排除掉已考慮過的位置。接著考慮如果第一個1選擇放入位置1,則第二個1排除位置0和1後還有2-9共8種選擇。依此類推,根據第一個1的位置選擇不同,則有9(p0), 8(p1), 7(p2), 6(p3), 5(p4), 4(p5), 3(p6), 2(p7), 1(p8), 0(p9)種選擇,小括號內的p0-9為第一個1的選擇位置