मान लीजिए कि हमारे पास एक बाइनरी स्ट्रिंग है, एक और पूर्णांक 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