[問題] 利用整數的位元運算,列舉所有組合

作者: xxxx9659 (嘎嘎嘎嘎嘎)   2022-01-24 19:22:40
最近在想一個問題,想要用一個整數,來代表一種組合
然後把 C(28, 5) 的所有組合,快速輪詢過一遍
C(28, 5) = 98280 有點大不好舉例,拿 C(6, 3) = 20 來當例子
var state = 56; //代表二進位的 111000
do {
console.log( state );
} while ( state = next(state) );
迴圈會印出以下20個值
56 //代表二進位的 111000
52 //代表二進位的 110100
50 //代表二進位的 110010
49 //代表二進位的 110001
44 //代表二進位的 101100
42 //代表二進位的 101010
41 //代表二進位的 101001
38 //代表二進位的 100110
37 //代表二進位的 100101
35 //代表二進位的 100011
28 //代表二進位的 011100
26 //代表二進位的 011010
25 //代表二進位的 011001
22 //代表二進位的 010110
21 //代表二進位的 010101
19 //代表二進位的 010011
14 //代表二進位的 001110
13 //代表二進位的 001101
11 //代表二進位的 001011
7 //代表二進位的 000111
位元運算 a & (a-1) 可以迅速的拔掉最低位元的1
左移右移 << >> 感覺也很好用
就在想說,能不能利用這種位元運算的高效率特性,來實作 next()
但是 next() 我還沒有實作出來... 不知道是不是真的可行
想說問問看各位大大的看法
作者: fenzhang (分帳)   2022-01-24 20:05:00
作者: FRAXIS (喔喔)   2022-01-25 02:25:00
搜尋 Gosper's hack 就有了 Wikipedia 上有解釋
作者: xxxx9659 (嘎嘎嘎嘎嘎)   2022-01-25 17:14:00
感謝樓上兩位大大!!

Links booklink

Contact Us: admin [ a t ] ucptt.com