ধরুন আমাদের একটি সংখ্যা k আছে। n সেট-বিটের সাথে k-বিট সংখ্যার সম্ভাব্য সকল সমন্বয় খুঁজুন যেখানে 1 <=n <=k। ফলস্বরূপ আমরা প্রথমে একটি সেট বিট সহ সমস্ত সংখ্যা প্রিন্ট করব, তারপরে দুটি বিট সেট সহ সংখ্যাগুলি, সমস্ত বিট সেট করা সংখ্যা পর্যন্ত। যদি দুটি সংখ্যার একই সংখ্যক সেট বিট থাকে, তাহলে ছোট সংখ্যাটি প্রথমে আসে। সুতরাং k =3 হলে, সংখ্যা হবে [001, 010, 100, 011, 101, 110, 111]
এখানে আমরা n সেট-বিটের সাথে k-বিট সংখ্যার সম্ভাব্য সকল সমন্বয় খুঁজে পেতে ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব যেখানে 1 <=n <=k। এই সমস্যাটিকেও দুই ভাগে ভাগ করা যায়। আমরা k দৈর্ঘ্যের সমস্ত সংমিশ্রণ খুঁজে পাব যেখানে 1s-এর n সংখ্যা 0-এর উপসর্গ দিয়ে k – 1 দৈর্ঘ্যের সমস্ত সংমিশ্রণে n-এর সাথে এবং 1-এর দৈর্ঘ্য k – 1-এর সাথে n – 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
