หาการจัดเรียงทั้งหมดของตัวเลข k-bit ที่มี n บิตเซต โดย 1 <= n <= k เรียงลำดับใน C++

สมมติว่ามีตัวเลข k หาการจัดเรียงที่เป็นไปได้ทั้งหมดของตัวเลข k-bit ที่มี n บิตเซต (Set bits) โดยที่ 1 <= n <= k ผลลัพธ์เราจะพิมพ์ตัวเลขทั้งหมดที่มีบิตเซต 1 ตัวก่อน ตามด้วยตัวเลขที่มีบิตเซต 2 ตัว จนถึงตัวเลขที่บิตทั้งหมดเป็นเซต หากตัวเลขสองตัวมีจำนวนบิตเซตเท่ากัน ตัวเลขที่เล็กกว่าจะมาก่อน ดังนั้นถ้า k = 3 ตัวเลขจะเป็น [001, 010, 100, 011, 101, 110, 111]

ที่นี่เราจะใช้แนวทาง Dynamic Programming เพื่อหาการจัดเรียงที่เป็นไปได้ทั้งหมดของตัวเลข k-bit ที่มี n บิตเซต โดยที่ 1 <= n <= k ปัญหานี้ยังสามารถแบ่งออกเป็นสองส่วนได้ เราจะหาการจัดเรียงทั้งหมดของความยาว k ที่มี n จำนวน 1 โดยการต่อ 0 หน้าการจัดเรียงความยาว k – 1 ที่มี n ตัว 1 และต่อ 1 หน้าการจัดเรียงความยาว 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