C ++を使用して、バイナリ文字列の1から始まる一意の順列の数を見つけます

与えられた問題では、0と1で構成される文字列が与えられます。文字列が1で始まるような順列の総数を見つける必要があります。答えは膨大な数になる可能性があるため、1000000007のmodとして出力します。

Input : str ="10101001001"
Output : 210

Input : str ="101110011"
Output : 56

いくつかの組み合わせ論を適用し、この問題を解決するためにいくつかの式を構築することによって、与えられた問題を解決します。

解決策を見つけるためのアプローチ

このアプローチでは、0と1の数を計算します。ここで、nが文字列に存在する1の数であり、mが文字列に存在する0の数であり、Lが指定された文字列の長さであると仮定すると、この問題を解決するために作成する式は（L-1 ）！/（n-1）！ * m！。

例

#include <bits/stdc++.h>
#define MOD 1000000007 // defining 1e9 + 7 as MOD

using namespace std;

long long fact(long long n) {
   if(n <= 1)
   return 1;
   return ((n % MOD) * (fact(n-1) % MOD)) % MOD;
}
int main() {
   string s = "101110011";
   long long L = s.size(); // length of given string
   long long count_1 = 0, count_0 = 0; // keeping count of 1's and 0's
   for(auto x : s) {
      if(x == '1')
         count_1++; // frequency of 1's
      else
        count_0++; // frequency of 0's
   }
   if(count_1 == 0){
      cout << "0\n"; // if string only consists of 0's so our answer will be 0
   } else {
      long long factL = fact(L-1); // (L-1)!
      long long factn = fact(count_1 - 1); // (n-1)!
      long long factm = fact(count_0); // m!
      long long ans = factL / (factn * factm); // putting the formula
      cout << ans << "\n";
   }
   return 0;
}

出力

56

指定されたプログラムの時間計算量はO（N）です。ここで、nは指定された文字列の長さです。

上記のコードの説明

このアプローチでは、文字列内に存在する1と0の数を数えています。最初に1つ配置し、長さL-1の文字列で0と1の可能なすべての順列を定式化します。したがって、これを定式化することにより、 （L-1）の式を取得してください！ /（n-1）！ * m！ここで（n-1）！残りの1とmの順列です！は0の順列です。

結論

この記事では、いくつかの組み合わせ論を適用してその式を作成することにより、バイナリ文字列の1から始まる一意の順列の数を見つける問題を解決します。

また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（Normal）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。