Différents nombres obtenus en générant toutes les permutations d'une chaîne binaire

Énoncé du problème

On nous donne une chaîne binaire str de longueur N. Nous devons trouver toutes les permutations de cette chaîne, les convertir en valeurs décimales et renvoyer toutes les valeurs décimales uniques.

Exemple

Entrez

str = ‘1’

Sortie

[1]

Instructions

Toutes les permutations de « 1 » sont simplement « 1 ». La valeur décimale associée à « 1 » est donc égale à 1.

Entrez

str = ‘10’

Sortie

[1, 2]

Instructions

La disposition de « 10 » est uniquement « 01 » et « 10 », qui sont respectivement équivalents à 1 et 2.

Entrez

‘101’

Sortie

[3, 5, 6]

Instructions

Toutes les permutations possibles de "101" sont "110", "101", "110", "011", "101" et "011", si nous les convertissons en nombres décimaux, nous obtenons 3, 5 et 6 décimales uniques. Nombres.

Méthode 1

Dans la première méthode, nous utiliserons le backtracing pour obtenir toutes les permutations de la chaîne binaire. Après cela, nous convertissons la permutation binaire en valeurs décimales et utilisons cet ensemble pour sélectionner la valeur décimale unique. Nous allons convertir le décimal en binaire en utilisant la méthode pow() et la boucle for.

Algorithme

• Étape 1 - Définissez la fonction "getDecimalPermutations()" pour obtenir la valeur décimale résultante.

• Étape 2 - Exécutez la fonction "getBinaryPermutations()" pour obtenir toutes les permutations binaires de la chaîne. De plus, les chaînes, les index gauche et droit et les vecteurs de permutation sont transmis comme arguments.

• Étape 2.1 - Dans la fonction "getBinaryPermutations()", si les indices gauche et droit sont égaux, poussez la chaîne résultante dans la liste permutée.

• Étape 2.2 - Si les indices gauche et droit ne sont pas égaux, utilisez une boucle for pour parcourir la chaîne de l'index gauche à l'index droit.

• Étape 2.3 - Échangez les caractères au i-ème index et à l'index gauche dans la boucle for.

• Étape 2.4 - Appelez à nouveau la fonction "getBinaryPermutations" avec les mêmes paramètres et l'index "gauche + 1".

• Étape 2.5 - Échangez les caractères au i-ème index et à l'index de gauche à des fins de retour en arrière.

• Étape 3 - Créez une collection appelée "allDecimals". Après cela, parcourez toutes les permutations de la chaîne binaire.

• Étape 4 - Appelez la fonction bToD() pour convertir le binaire en décimal.

• Étape 4.1 - Dans la fonction bToD(), initialisez la variable décimale avec la valeur 0.

• Étape 4.2 - Utilisez une boucle for pour parcourir la chaîne binaire en commençant par la fin et ajoutez '(num[i] - '0') * pow(2, j )' pour la convertir en valeur décimale.

• Étape 4.3 - Renvoie la valeur décimale.

• Étape 5 - Dans la fonction "getDecimalPermutations", insérez la valeur décimale renvoyée par la fonction bToD().

• Étape 6 - Imprimez toutes les valeurs de l'ensemble, qui contiendront des valeurs décimales uniques.

Exemple

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Function to convert binary to decimal
int bToD(string num){
   int decimal = 0;
   for (int i = num.size() - 1, j = 0; i >= 0; i--, j++){
      decimal += (num[i] - '0') * pow(2, j);
   }
   return decimal;
}
// Function to get all permutations of a binary string
void getBinaryPermutations(string str, int left, int right, vector<string> &permutations){
   // Base case
   if (left == right){
      // push_back() function is used to push elements into a vector from the back
      permutations.push_back(str);
   } else {
      // Permutations made
      for (int i = left; i <= right; i++){
         // Swapping done
         swap(str[left], str[i]);
         // Recursion called for next index (left + 1)
         getBinaryPermutations(str, left + 1, right, permutations);
         // Backtrack
         swap(str[left], str[i]);
      }
   }
}
void getDecimalPermutations(string str){
   vector<string> permutations;
   getBinaryPermutations(str, 0, str.length() - 1, permutations);
   set<int> allDecimals;
   for (const auto &p : permutations){
      allDecimals.insert(bToD(p));
   }
   cout << "All decimal numbers which we can achieve using permutations are " << endl;
   for (const auto &d : allDecimals){
      cout << d << " ";
   }
}
int main(){
   string bString = "101";
   getDecimalPermutations(bString);
   return 0;
}

Sortie

All decimal numbers which we can achieve using permutations are 
3 5 6

• Complexité temporelle - O(n!). La complexité temporelle de la fonction « getBinaryPermutations() » est « n ! » car nous utilisons le backtracking pour trouver toutes les permutations. La complexité temporelle de la fonction bToD() est O(n).

• Complexité spatiale - O(n!). Chaque chaîne a n!permutations que nous stockons dans la liste.

Méthode 2

Dans cette méthode, au lieu de la méthode de retour en arrière, nous utiliserons la fonction next_permutation() de C++ pour générer la permutation de chaîne binaire. De plus, nous avons modifié la méthode de conversion binaire en décimal.

Algorithme

• Étape 1 - Définissez l'ensemble "allNumbers".

• Étape 2 - La méthode sort() est utilisée pour trier les chaînes binaires.

• Étape 3 - Utilisez une boucle do-while pour parcourir chaque permutation de la chaîne.

• Étape 4 - Dans la boucle do-while, appelez la fonction bToD() en passant une chaîne comme paramètre pour convertir le binaire en nombre décimal.

• Étape 4.1 - Dans la fonction bToD(), définissez la variable "currentBase" et initialisez-la à 1.

• Étape 4.2 - Utilisez une boucle for et parcourez la chaîne en commençant par le dernier index.

• Étape 4.3 - Dans la boucle for, si le caractère actuel est égal à « 1 », nous devons ajouter la valeur currentBase au « nombre_décimal ».

• Étape 4.4 - Multipliez currentBase par 2.

• Étape 5 - Insérez le nombre décimal dans l'ensemble "allNumber".

• Étape 6 - Utilisez la méthode next_permutation() dans la condition de la boucle do-while car elle retournera vrai si la prochaine permutation de la chaîne existe.

• Étape 7 - Imprimez tous les nombres ajoutés dans "allNumbers" pour obtenir des nombres décimaux uniques associés à toutes les permutations de la chaîne binaire donnée.

示例

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
int bToD(string num){
   int decimal_number = 0;
   // Initializing base value to 1, and it increases by power of 2 in each iteration
   int currentBase = 1;
   for (int i = num.length() - 1; i >= 0; i--){
      if (num[i] == '1'){
         decimal_number += currentBase;
      }
      currentBase = currentBase * 2;
   }
   return decimal_number;
}
void getDecimalPermutations(string str){
   // create set
   set<int> allNumbers;
   // sort the string
   sort(str.begin(), str.end());
   do {
      // convert binary string to decimal
      int result = bToD(str);
      // insert the decimal number to set
      allNumbers.insert(result);
      // get the next permutation
   } while (next_permutation(str.begin(), str.end()));
   //Print all distinct decimal numbers
   cout << "All decimal numbers which we can achieve using permutations are " << endl;
   for (auto num : allNumbers)
      cout << num << " ";
      cout << endl;
}
int main(){
   string bString = "101";
   getDecimalPermutations(bString);
   return 0;
}

输出

All decimal numbers which we can achieve using permutations are 
3 5 6

• 时间复杂度 - O(n*n!)。这里，next_permutations() 需要 O(n) 时间来找到一个排列，并且我们正在找到总共 n！排列。

• 空间复杂度 - O(n!)，因为我们将所有排列存储在列表中。

结论

我们学习了不同的方法来获取通过给定二进制字符串的所有排列获得的唯一十进制值。在第一种方法中，我们使用了回溯；在第二种方法中，我们使用了 next_permutation() 方法。

第二种方法的代码更清晰，但需要更多的时间和复杂性。

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!