Ermitteln Sie in C++ die Anzahl der eindeutigen Permutationen einer Binärzeichenfolge, die mit 1 beginnt

In der gegebenen Aufgabe erhalten wir eine Zeichenfolge bestehend aus 0 und 1. Wir müssen die Gesamtzahl aller Permutationen ermitteln, die mit 1 beginnen. Da die Antwort eine große Zahl sein kann, nehmen wir sie modulo 1000000007 und geben sie aus.

Input : str ="10101001001"
Output : 210

Input : str ="101110011"
Output : 56

Wir werden dieses Problem lösen, indem wir kombinatorische Mathematik anwenden und einige Formeln aufstellen.

Lösungsmethode

Bei dieser Methode zählen wir die Anzahl der Nullen und Einsen. Nehmen wir nun an, dass n die Anzahl der Einsen ist, die in unserer Zeichenfolge erscheinen, m die Anzahl der Nullen ist, die in unserer Zeichenfolge erscheinen, und L die Länge unserer gegebenen Zeichenfolge ist. Die Formel, die wir zur Lösung dieses Problems formulieren, lautet also (L- 1 )!/ (n-1)!.

Beispiel

#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&#39;s and 0&#39;s
   for(auto x : s) {
      if(x == &#39;1&#39;)
         count_1++; // frequency of 1&#39;s
      else
        count_0++; // frequency of 0&#39;s
   }
   if(count_1 == 0){
      cout << "0\n"; // if string only consists of 0&#39;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;
}

Ausgabe

56

Die zeitliche Komplexität des gegebenen Programms ist O(N), wobei n die Länge der gegebenen Zeichenfolge ist.

Erklärung des obigen Codes

Bei dieser Methode zählen wir die Anzahl der Einsen und Nullen im String, setzen nun eine 1 an den Anfang und formulieren nun alle möglichen Nullen im String der Länge L-1 und 1 Permutation. Durch die Formulierung dieser Permutation erhalten wir die Formel von (L-1)! / (n-1)!, wobei (n-1) die Permutation von 0 ist.

Fazit

In diesem Artikel haben wir das Problem gelöst, die Anzahl der eindeutigen Permutationen einer Binärzeichenfolge beginnend mit 1 zu ermitteln, indem wir einige Kombinatoriken angewendet und eine Formel formuliert haben.

Wir haben auch das C++-Programm und die vollständige Methode (normale Methode) gelernt, um dieses Problem zu lösen. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie finden diesen Artikel hilfreich.

Das obige ist der detaillierte Inhalt vonErmitteln Sie in C++ die Anzahl der eindeutigen Permutationen einer Binärzeichenfolge, die mit 1 beginnt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!