バイナリ文字列にC++で長さkのすべての順列が含まれているかどうかを確認します

バイナリ文字列、別の整数kがあるとします。文字列にkビットのバイナリのすべての順列が含まれていることを確認する必要があります。文字列が「11001」のようなものであり、K =2の場合、kビット数のすべての順列が必要であるとします。 （00、01、10、11）、指定された文字列にはすべての順列があります。したがって、これは有効な文字列です。

バイナリ文字列とkの値を取得することにより、バイナリシーケンスが一致するかどうかを確認する必要があります。バイナリシーケンスはサイズkで構成されています。したがって、2k個の異なるバイナリ順列があります。 k長のバイナリ値のすべての順列を文字列としてリストに格納し、リストに存在するすべての要素を指定された文字列のサブセットとして比較します。リストに存在するすべての文字列についてtrueが得られた場合、その文字列は有効です。そうでない場合は無効です。

例

#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