[問題] 例舉 k-bit 組合在一個當予的mask中

[dnol (舞秋風 憶白雲)]

各位大大好。後正在使用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://www.ptt.cc/bbs/C_and_CPP/M.1706066335.A.480.html
※ 編輯: dnol (211.21.176.170 臺灣), 01/24/2024 11:20:13
推 Dracarys: 直覺想到 std::next_permutation
推 oToToT: 只是要功能的話應該可以寫個遞迴函數枚舉?
→ dnol: 我目前是用遞迴加上vector存起來需要的組合
→ dnol: 但我在尋求，是否有神奇的bit operation可達到我的需求
→ lycantrope: 不是產生所有k=2的mask取AND?
推 stupid0319: mask有限量的話,直接弄一個 map list 就好了
→ FRAXIS: Gosper's Hack 就是你要找的
推 ddavid: Gosper's Hack 跟這題差一步是擺到 mask 中為 1 的位數上
→ ddavid: ，可以拿來取代我那篇的 generateCombinations，但還是需
→ ddavid: 要最後填位置的步驟
推 ddavid: 因為 Gosper's Hack 速度快的前提是每個 bit 都可以用，
→ ddavid: 才能用他那套位元運算加速
推 expiate: 用兩個for loop 做 bit operation可以滿足你的需求嗎
→ dnol: 謝謝大家的建議，Gosper's Hack給了我一些啟發，很有幫助