在猜數字遊戲 (電腦猜人)這篇文章裡，最後提到怎麼從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的選擇位置。第一個1放入位置9時，第二個1就沒位置可放入了，所以可能性為0種，因此全部可能性共有9+8+7+6+5+4+3+2+1=45種。
驗算一下，C(10,2)=10!/2!(10-2)!=10!/2!8!=45
;
根據上述的討論，可以以遞迴的方式實作出上述演算法。虛擬碼如下：
這個方法很簡單，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的選擇位置。第一個1放入位置9時，第二個1就沒位置可放入了，所以可能性為0種，因此全部可能性共有9+8+7+6+5+4+3+2+1=45種。
驗算一下，C(10,2)=10!/2!(10-2)!=10!/2!8!=45
;
根據上述的討論，可以以遞迴的方式實作出上述演算法。虛擬碼如下：
void C(int LeftPos, int Depth)
{
uint64 Flag = 1 << LeftPos;
for (int i = LeftPos; i < MaxPos; i++, Flag <<= 1) {
if (!(AllPosMask & Flag)) {
if (0 < Depth) {
AllPosMask |= Flag;
C(i + 1, Depth - 1);
AllPosMask &= ~Flag;
} else {
// Found it!
}
}
}
}
留言
張貼留言