作者ddavid (謊言接線生)
看板C_and_CPP
標題Re: [問題] 在一個給予的mask中，例舉所有k-bit 組合
時間Wed Jan 24 15:10:28 2024
※ 引述《dnol (舞秋風 憶白雲)》之銘言：
: 後目前面臨的問題是，
: how to enumerate all k-bit combinations for a given mask.
: 比如說。我有一個mask。1100101。當k=2時。
: 我想要有效率的例舉所有含有2個1的組合。如下。
: 0000101
: 0100001
: 1000001
: 0100100
: 1000100
: 1100000
: 請問有辦法只iterate k=2的case嗎?
說到頭來，這不就是 C(4, 2) 然後擺到可能的位數上去嗎？你看看這合不合你
需求。
裡面很多 4 啊 2 啊 {1, 4, 32, 64} 這些魔術數字或是輸出方式當然都可以一
般化，看你的需求。比如這邊是直接把 bit 的實際值加總，只是印出時才轉回 0101
表示，但你也可以 mask_bits 用位置 {0, 2, 5, 6} 來處理。
當然你會需要一小段程式取得 mask_bits 陣列。
若要做什麼事情，就在 cout 那邊做就好。
#include <iostream>
#include <bitset>
using namespace std;
int mask_bits[4] = {1, 4, 32, 64};
void generateCombinations(int n, int k, int sub_mask) {
if (k == 0) {
std::bitset<8> binary(sub_mask);
cout << binary << endl;
return;
}
for (int i = n - 1; i >= 0; i--) {
sub_mask += mask_bits[i];
generateCombinations(i, k - 1, sub_mask);
sub_mask -= mask_bits[i];
}
}
int main() {
generateCombinations(4, 2, 0);
return 0;
}
--
「珍貴的回憶？還不是跟夢一樣虛幻不實的東西？你想要什麼樣的回憶，我幫你
做出來啦！」
－－艾蜜思，謊言事務所實現使者
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.30.72 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1706080230.A.3C3.html
※ 編輯: ddavid (114.32.30.72 臺灣), 01/24/2024 15:13:15