作者xxxx9659 (嘎嘎嘎嘎嘎)
看板Prob_Solve
标题[问题] 利用整数的位元运算,列举所有组合
时间Mon Jan 24 19:22:40 2022
最近在想一个问题,想要用一个整数,来代表一种组合
然後把 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() 我还没有实作出来... 不知道是不是真的可行
想说问问看各位大大的看法
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 125.227.45.150 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1643023362.A.417.html
3F:推 FRAXIS: 搜寻 Gosper's hack 就有了 Wikipedia 上有解释 01/25 02:25
4F:→ xxxx9659: 感谢楼上两位大大!! 01/25 17:14