C++でセットビットがn個（1≤n≤k）のkビット数の全組み合わせをソート順に生成する方法

数値 k が与えられたとき、セットビット（値が1になっているビット）が n 個（1 ≤ n ≤ k）である k ビット数のすべての組み合わせを求める問題です。出力は、セットビットが1個の数から始まり、2個、3個と順に続き、最後にすべてのビットが1になった数まで表示します。また、セットビットの数が同じ数同士については、値が小さい方を先に出力します。

例えば k = 3 の場合、出力される数の並びは [001, 010, 100, 011, 101, 110, 111] となります。

アプローチ：動的計画法

ここでは動的計画法（DP）を用いて、セットビットが n 個（1 ≤ n ≤ k）である k ビット数のすべての組み合わせを求めます。この問題は次の2つの部分に分解できます。長さ k のビット列のうちセットビットが n 個のものは、以下の2種類の組み合わせから構成されます。

• 長さ k − 1 でセットビットが n 個のすべての組み合わせの先頭に「0」を付けたもの
• 長さ k − 1 でセットビットが n − 1 個のすべての組み合わせの先頭に「1」を付けたもの

この漸化式を利用し、短い桁数から順にテーブルを埋めていくことで、すべての組み合わせを効率よく生成できます。

C++での実装例

#include<iostream>
#include<vector>
#define K 16
using namespace std;
vector<string> table[K][K];
void getCombinations(int k) {
    string str = "";
    for (int bit = 0; bit <= k; bit++) {
        table[bit][0].push_back(str);
        str = str + "0";
    }
    for (int bit = 1; bit <= k; bit++) {
        for (int n = 1; n <= bit; n++) {
            for (string str : table[bit - 1][n])
                table[bit][n].push_back("0" + str);
            for (string str : table[bit - 1][n - 1])
                table[bit][n].push_back("1" + str);
        }
    }
    for (int n = 1; n <= k; n++) {
        for (string str : table[k][n])
        cout << str << " ";
        cout << endl;
    }
}
int main() {
    int k = 4;
    getCombinations(k);
}

実行結果

0001 0010 0100 1000
0011 0101 0110 1001 1010 1100
0111 1011 1101 1110
1111

コードの解説

• table[bit][n] は、「bit 桁のうちセットビットが n 個であるすべてのビット列」を格納する2次元配列です。
• まず初期化として、table[bit][0]（セットビットが0個の場合）に「000…0」という全ゼロの文字列を登録します。
• その後、桁数を1ずつ増やしながら、前述の漸化式に従って新しい組み合わせを順次生成していきます。
• 最後に、セットビットの数が少ない順（同じ場合は数値の昇順）で結果を出力します。「0」を付けた組み合わせが常に「1」を付けたものより先に追加されるため、自然とソートされた順序になります。

このアルゴリズムでは、生成されるビット列の総数が 2^k − 1 個になるため、計算量は O(2^k × k) となります。k の値が大きくなると組み合わせの数が指数関数的に増加するため、この実装では k を最大16までに制限しています。