作者dnol (舞秋风 忆白云)
看板C_and_CPP
标题[问题] 例举 k-bit 组合在一个当予的mask中
时间Wed Jan 24 11:18:53 2024
各位大大好。後正在使用C开发一个演算法。
後目前面临的问题是，
how to enumerate all k-bit combinations for a given mask.
比如说。我有一个mask。1100101。当k=2时。
我想要有效率的例举所有含有2个1的组合。如下。
0000101
0100001
1000001
0100100
1000100
1100000
我目前是用下面的code 产生出所有的sub-mask，但然跳掉k!=2的case。
for(unsigned sub_mask = (mask - 1) & mask; sub_mask;
sub_mask = (sub_mask - 1) & mask) {
if(__builtin_popcount(sub_mask) != k ) //k=2
continue;
...
}
请问有办法只iterate k=2的case吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 211.21.176.170 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1706066335.A.480.html
※ 编辑: dnol (211.21.176.170 台湾), 01/24/2024 11:20:13
1F：推 Dracarys: 直觉想到 std::next_permutation 01/24 11:52
2F：推 oToToT: 只是要功能的话应该可以写个递回函数枚举? 01/24 11:55
3F：→ dnol: 我目前是用递回加上vector存起来需要的组合 01/24 12:00
4F：→ dnol: 但我在寻求，是否有神奇的bit operation可达到我的需求 01/24 12:01
5F：→ lycantrope: 不是产生所有k=2的mask取AND? 01/24 12:16
6F：推 stupid0319: mask有限量的话,直接弄一个 map list 就好了 01/24 13:15
7F：→ FRAXIS: Gosper's Hack 就是你要找的 01/25 06:40
8F：推 ddavid: Gosper's Hack 跟这题差一步是摆到 mask 中为 1 的位数上 01/25 10:01
9F：→ ddavid: ，可以拿来取代我那篇的 generateCombinations，但还是需 01/25 10:03
10F：→ ddavid: 要最後填位置的步骤 01/25 10:03
11F：推 ddavid: 因为 Gosper's Hack 速度快的前提是每个 bit 都可以用， 01/25 10:08
12F：→ ddavid: 才能用他那套位元运算加速 01/25 10:09
13F：推 expiate: 用两个for loop 做 bit operation可以满足你的需求吗 01/27 08:14
14F：→ dnol: 谢谢大家的建议，Gosper's Hack给了我一些启发，很有帮助 02/01 10:17