作者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/m.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