สมมติว่าเรามีสตริงเลขฐานสอง ซึ่งเป็นจำนวนเต็ม 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
