C++에서 이진 문자열에 길이가 k인 모든 순열이 포함되어 있는지 확인

이진 문자열, 또 다른 정수 k가 있다고 가정합니다. 문자열에 k 비트 바이너리의 모든 순열이 포함되어 있는지 확인해야 합니다. 문자열이 "11001"과 같다고 가정하고 K =2이면 k 비트 숫자의 모든 순열을 가져야 합니다. (00, 01, 10, 11), 주어진 문자열에는 모든 순열이 있습니다. 따라서 이것은 유효한 문자열입니다.

이진 문자열과 k 값을 취하여 이진 시퀀스가 ​​일치하는지 여부를 확인해야 합니다. 이진 시퀀스는 크기 k로 구성됩니다. 따라서 2,000개의 서로 다른 이진 순열이 있을 것입니다. 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