ধরুন আমাদের একটি বাইনারি স্ট্রিং আছে, আরেকটি পূর্ণসংখ্যা k। আমাদের চেক করতে হবে যে স্ট্রিং-এ k বিটের বাইনারি সব পারমুটেশন রয়েছে। ধরুন একটি স্ট্রিং "11001" এর মতো, এবং যদি K =2, তাহলে এটিতে অবশ্যই k বিট সংখ্যার সমস্ত পারমুটেশন থাকতে হবে। (00, 01, 10, 11), প্রদত্ত স্ট্রিংটিতে সমস্ত স্থানান্তর রয়েছে। তাই এটি বৈধ স্ট্রিং।
বাইনারি স্ট্রিং এবং k এর মান নিয়ে, আমাদের পরীক্ষা করতে হবে বাইনারি সিকোয়েন্স মিলছে কি না। বাইনারি ক্রমটি k আকার দিয়ে তৈরি। তাই বিভিন্ন বাইনারি পারমুটেশনের 2k সংখ্যা থাকবে। আমরা একটি তালিকায় স্ট্রিং হিসাবে k দৈর্ঘ্যের বাইনারি মানের সমস্ত পারমুটেশন সংরক্ষণ করব, তারপর প্রদত্ত স্ট্রিংটির উপসেট হিসাবে তালিকায় উপস্থিত সমস্ত উপাদানের তুলনা করব। যদি আমরা তালিকায় উপস্থিত সমস্ত স্ট্রিংয়ের জন্য সত্য পাই, তাহলে স্ট্রিংটি বৈধ, অন্যথায় নয়৷
উদাহরণ
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<string> binaryPermutations(int k){
vector<string> list;
int n = 0;
string bin_str = "";
for(int i = 0; i<k; i++){
bin_str += "0";
}
int limit = pow(2, k);
list.push_back(bin_str);
for(int i=1; i<limit; i++){
int j = 0;
while(j <= k){
if(bin_str[k-1-j] == '0'){
bin_str[k - 1 - j] = '1';
break;
} else {
bin_str[k - 1 - j] = '0';
j++;
}
}
list.push_back(bin_str);
}
return list;
}
bool hasAllPermutation(string str, int k){
vector<string> list = binaryPermutations(k);
for(int i = 0; i<list.size(); i++){
string substr = list[i];
std::size_t found = str.find(substr);
if(found == std::string::npos){
return false;
}
}
return true;
}
int main() {
int k = 2;
string str = "11001";
if(hasAllPermutation(str, k)){
cout << "Has All Permutations";
} else {
cout << "Not All Permutations are found";
}
} আউটপুট
Has All Permutations
