k-বিট সংখ্যার সব কম্বিনেশন খুঁজে বের করা যাতে n বিট সেট থাকে 1 <= n <= k সর্টেড অর্ডারে C++-তে

মনে করুন আমাদের একটি সংখ্যা k আছে। k-বিট সংখ্যার সব সম্ভাব্য কম্বিনেশন বের করতে হবে যাতে n সেট-বিট থাকে যেখানে 1 <= n <= k। ফলাফল হিসেবে আমরা সব সংখ্যা প্রিন্ট করব যাতে একটা সেট বিট আছে প্রথমে, তারপর দুইটা বিট সেট, এবং এভাবে চলতে থাকব যতক্ষণ না সব বিট সেট হয়। যদি দুটি সংখ্যার একই সংখ্যক সেট বিট থাকে, তবে ছোট সংখ্যাটি আগে আসবে। তাই যদি k = 3 হয়, তবে সংখ্যাগুলো হবে [001, 010, 100, 011, 101, 110, 111]

এখানে আমরা ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব k-বিট সংখ্যার সব সম্ভাব্য কম্বিনেশন n সেট-বিটসহ যেখানে 1 <= n <= k বের করতে। এই সমস্যাটি দুটি অংশে ভাগ করা যেতে পারে। আমরা দৈর্ঘ্য k-র সব কম্বিনেশন বের করব যেখানে n সংখ্যক 1 থাকবে দৈর্ঘ্য k-1-এর সব কম্বিনেশনের সাথে 0 প্রিফিক্স করে এবং দৈর্ঘ্য k-1-এর সব কম্বিনেশনের সাথে 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