2014年1月12日 星期日

快速組合算法(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的選擇位置。第一個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!
      }
    }
  }
}


Related Posts Plugin for WordPress, Blogger...