Rechercher toute permutation qui n'existe pas dans un tableau de chaînes binaires de taille donnée

Dans ce problème, nous devons trouver toutes les chaînes binaires manquantes de longueur N dans un tableau. Nous pouvons résoudre ce problème en recherchant toutes les permutations d’une chaîne binaire de longueur N et en vérifiant quelles permutations n’existent pas dans le tableau. Nous verrons ici des méthodes itératives et récursives pour résoudre ce problème.

Énoncé du problème - Nous avons reçu un tableau arr[] de longueur N contenant des chaînes binaires de différentes longueurs. Nous devons trouver toutes les chaînes binaires manquantes de longueur N dans le tableau.

Exemple Exemple

Entrée – arr = {"111", "001", "100", "110"}, N = 3

Sortie – [000, 010, 011, 101]

Explication – Il existe 8 chaînes binaires de longueur 3, car 2 élevé à la puissance trois est égal à 8. Ainsi, il imprime les 4 chaînes binaires manquantes de longueur 3.

Entrée – str = {'00', '10', '11'}, N = 2

Sortie –[‘01’]

Explication – « 01 » est manquant dans le tableau, il sera donc imprimé dans la sortie.

Méthode 1

Ici, nous utiliserons la méthode itérative pour trouver toutes les chaînes binaires possibles de longueur N. Après cela, nous vérifierons si la chaîne existe dans le tableau. Si elle n'existe pas, nous imprimons la chaîne.

Algorithme

• Définissez la collection et utilisez la méthode insert() pour ajouter toutes les chaînes du tableau à la collection.

• Initialisez la variable total avec 2N, où 2N est le nombre total de chaînes de longueur N

• Définissez la variable 'cnt' et initialisez-la à zéro pour stocker le nombre total de combinaisons manquantes.

• Utilisez une boucle pour effectuer le nombre « total » d'itérations afin de trouver toutes les chaînes binaires de longueur N.

• Dans la boucle, initialisez la variable chaîne "num" avec une chaîne vide.

• Utilisez des boucles imbriquées pour un total de N itérations et à partir de la dernière itération, créez une chaîne de longueur N.

• Utilisez la méthode find() pour vérifier si la collection contient la chaîne actuelle. Si tel est le cas, augmentez la valeur de « cnt » de 1.

• Si la chaîne n'est pas dans la carte, imprimez-la pour l'afficher dans la sortie

• Si la valeur de "cnt" est égale au nombre total, cela signifie que toutes les chaînes de longueur N existent dans le tableau et "-1" est imprimé.

Exemple

#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;
}

Sortie

000, 010, 011, 101, 

Complexité temporelle - O(N*2N), où O(N) est utilisé pour vérifier si la chaîne existe dans le tableau et O(2N) est utilisé pour trouver toutes les permutations possibles.

Complexité spatiale - O(N) car nous utilisons set pour stocker les chaînes.

Méthode 2

Dans cette méthode, nous montrons en utilisant la méthode récursive pour trouver toutes les chaînes binaires possibles de longueur N.

Algorithme

• Définissez une collection et insérez toutes les valeurs du tableau dans la collection.

• Appelez la fonction generateCombinations() pour générer toutes les combinaisons de chaînes binaires

• Définissez le cas de base dans la fonction generateCombinations(). Si l'index est égal à N, alors currentCombination est ajouté à la liste.

• Après avoir ajouté « 0 » ou « 1 » à la combinaison actuelle, appelez la fonction generateCombinations() de manière récursive.

• Après avoir obtenu toutes les combinaisons, vérifiez quelles combinaisons sont présentes dans le tableau et lesquelles ne le sont pas. Imprimez également les combinaisons manquantes à afficher dans la sortie.

Exemple

#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;
}

Sortie

000
010
011
101

Complexité temporelle - O(N*2N)

Complexité spatiale - O(2N) puisque nous stockons toutes les combinaisons dans un tableau.

Les deux méthodes utilisent la même logique pour résoudre le problème. La première méthode utilise une technique itérative pour trouver toutes les combinaisons de chaînes binaires de longueur N, ce qui est plus rapide que la technique récursive utilisée dans la seconde méthode. De plus, la deuxième méthode consomme plus d’espace que la première méthode.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!