Finden Sie alle Permutationen, die in einem binären String-Array einer bestimmten Größe nicht vorhanden sind

In diesem Problem müssen wir alle fehlenden Binärzeichenfolgen der Länge N aus einem Array finden. Wir können dieses Problem lösen, indem wir alle Permutationen einer binären Zeichenfolge der Länge N finden und prüfen, welche Permutationen im Array nicht vorhanden sind. Hier werden wir iterative und rekursive Methoden zur Lösung dieses Problems sehen.

Problemstellung – Wir haben ein Array arr[] der Länge N erhalten, das Binärzeichenfolgen unterschiedlicher Länge enthält. Wir müssen alle fehlenden Binärzeichenfolgen der Länge N aus dem Array finden.

Beispiel Beispiel

Eingabe – arr = {"111", "001", "100", "110"}, N = 3

Ausgabe – [000, 010, 011, 101]

Erläuterung – Es gibt 8 binäre Zeichenfolgen der Länge 3, da 2 in der dritten Potenz gleich 8 ist. Es gibt also die fehlenden 4 Binärzeichenfolgen der Länge 3 aus.

Eingabe – str = {‘00’, ‘10’, ‘11’}, N = 2

Ausgabe –[‘01’]

Erklärung – „01“ fehlt im Array und wird daher in der Ausgabe gedruckt.

Methode 1

Hier verwenden wir die iterative Methode, um alle möglichen Binärzeichenfolgen der Länge N zu finden. Danach prüfen wir, ob die Zeichenfolge im Array vorhanden ist. Wenn es nicht existiert, drucken wir die Zeichenfolge.

Algorithmus

• Definieren Sie die Sammlung und verwenden Sie die Methode insert(), um alle Zeichenfolgen im Array zur Sammlung hinzuzufügen.

• Initialisieren Sie die Gesamtvariable mit 2N, wobei 2N die Gesamtzahl der Zeichenfolgen der Länge N ist

• Definieren Sie die Variable „cnt“ und initialisieren Sie sie auf Null, um die Gesamtzahl der fehlenden Kombinationen zu speichern.

• Verwenden Sie eine Schleife, um die „Gesamtzahl“ der Iterationen zu ermitteln und alle binären Zeichenfolgen der Länge N zu finden.

• Initialisieren Sie in der Schleife die String-Variable „num“ mit einem leeren String.

• Verwenden Sie verschachtelte Schleifen für insgesamt N Iterationen und erstellen Sie ausgehend von der letzten Iteration eine Zeichenfolge der Länge N.

• Verwenden Sie die Methode find(), um zu überprüfen, ob die Sammlung die aktuelle Zeichenfolge enthält. Wenn ja, erhöhen Sie den Wert von „cnt“ um 1.

• Wenn die Zeichenfolge nicht in der Karte enthalten ist, drucken Sie sie aus, um sie in der Ausgabe anzuzeigen

• Wenn der Wert von „cnt“ gleich der Gesamtzahl ist, bedeutet dies, dass alle Zeichenfolgen der Länge N im Array vorhanden sind und „-1“ gedruckt wird.

Beispiel

#include <bits/stdc++.h>
using namespace std;
// function to print missing combinations of a binary string of length N in an array
void printMissingCombinations(vector<string> &arr, int N) {
   unordered_set<string> set;
   // insert all the strings in the set
   for (string temp : arr) {
      set.insert(temp);
   }
   // get total combinations for the string of length N
   int total = (int)pow(2, N);
   // To store combinations that are present in an array
   int cnt = 0;
   // find all the combinations
   for (int p = 0; p < total; p++) {
      // Initialize empty binary string
      string bin = "";
      for (int q = N - 1; q >= 0; q--) {
          // If the qth bit is set, append '1'; append '0'.
          if (p & (1 << q)) {
              bin += '1';
          } else {
              bin += '0';
          }
      }
      // If the combination is present in an array, increment cnt
      if (set.find(bin) != set.end()) {
          cnt++;
          continue;
      } else {
          cout << bin << ", ";
      }
   }
   // If all combinations are present in an array, print -1
   if (cnt == total) {
      cout << "-1";
   }
}
int main() {
   int N = 3;
   vector<string> arr = {"111", "001", "100", "110"};
   printMissingCombinations(arr, N);
   return 0;
}

Ausgabe

000, 010, 011, 101, 

Zeitkomplexität – O(N*2N), wobei O(N) verwendet wird, um zu prüfen, ob die Zeichenfolge im Array vorhanden ist, und O(2N) verwendet wird, um alle möglichen Permutationen zu finden.

Raumkomplexität – O(N), weil wir set zum Speichern von Strings verwenden.

Methode 2

In dieser Methode zeigen wir, wie wir mit der rekursiven Methode alle möglichen Binärzeichenfolgen der Länge N finden.

Algorithmus

• Definieren Sie eine Sammlung und fügen Sie alle Array-Werte in die Sammlung ein.

• Rufen Sie die Funktion „generateCombinations()“ auf, um alle Kombinationen von Binärzeichenfolgen zu generieren

• Definieren Sie den Basisfall in der Funktion „generateCombinations()“. Wenn der Index gleich N ist, wird currentCombination zur Liste hinzugefügt.

• Nachdem Sie „0“ oder „1“ zur aktuellen Kombination hinzugefügt haben, rufen Sie die Funktion „generateCombinations()“ rekursiv auf.

• Nachdem Sie alle Kombinationen erhalten haben, prüfen Sie, welche Kombinationen im Array vorhanden sind und welche nicht. Drucken Sie außerdem die fehlenden Kombinationen aus, um sie in der Ausgabe anzuzeigen.

Beispiel

#include <bits/stdc++.h>
using namespace std;
// Function to generate all possible combinations of binary strings
void generateCombinations(int index, int N, string currentCombination, vector<string> &combinations) {
   // Base case: if we have reached the desired length N, add the combination to the vector
   if (index == N) {
      combinations.push_back(currentCombination);
      return;
   }
   // Recursively generate combinations by trying both 0 and 1 at the current index
   generateCombinations(index + 1, N, currentCombination + "0", combinations);
   generateCombinations(index + 1, N, currentCombination + "1", combinations);
}
// function to print missing combinations of a binary string of length N in an array
void printMissingCombinations(vector<string> &arr, int N) {    
   unordered_set<string> set;
   // insert all the strings in the set
   for (string str : arr) {
      set.insert(str);
   }
   // generating all combinations of binary strings of length N
   vector<string> combinations;
   generateCombinations(0, N, "", combinations);
   // Traverse all the combinations and check if it is present in the set or not
   for (string str : combinations) {
      // If the combination is not present in the set, print it
      if (set.find(str) == set.end()) {
          cout << str << endl;
      }
   }

   return;
}
int main(){
   int N = 3;
   vector<string> arr = {"111", "001", "100", "110"};
   printMissingCombinations(arr, N);
   return 0;
}

Ausgabe

000
010
011
101

Zeitkomplexität – O(N*2N)

Raumkomplexität – O(2N), da wir alle Kombinationen im Array speichern.

Beide Methoden verwenden dieselbe Logik, um das Problem zu lösen. Die erste Methode verwendet eine iterative Technik, um alle Kombinationen binärer Zeichenfolgen der Länge N zu finden, was schneller ist als die rekursive Technik, die in der zweiten Methode verwendet wird. Außerdem verbraucht die zweite Methode mehr Platz als die erste Methode.

Das obige ist der detaillierte Inhalt vonFinden Sie alle Permutationen, die in einem binären String-Array einer bestimmten Größe nicht vorhanden sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!