C++でソートされた順序で1<=n<=kであるnビットが設定されたkビット数のすべての組み合わせを検索します

数kがあるとします。 1 <=n<=kであるn個のセットビットを持つkビット数のすべての可能な組み合わせを見つけます。結果として、最初に1セットのビットを持つすべての数値を出力し、次に2ビットが設定された数値を、すべてのビットが設定される数まで出力します。 2つの数値のセットビット数が同じである場合は、小さい方の数値が最初になります。したがって、k =3の場合、数値は[001、010、100、011、101、110、111]

ここでは、動的計画法を使用して、1 <=n<=kであるn個のセットビットを持つkビット数のすべての可能な組み合わせを見つけます。この問題は、2つの部分に分けることもできます。長さkのすべての組み合わせを見つけます。ここでn個の1は、長さk – 1とn個のすべての組み合わせに0を付け、長さk –1とn–1個のすべての組み合わせに1を付けます。

例

#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