Verschiedene Zahlen, die durch Generieren aller Permutationen einer Binärzeichenfolge erhalten werden

Problemstellung

Wir erhalten eine binäre Zeichenfolge str der Länge N. Wir müssen alle Permutationen dieser Zeichenfolge finden, sie in Dezimalwerte umwandeln und alle eindeutigen Dezimalwerte zurückgeben.

Beispiel

Eintreten

str = ‘1’

Ausgabe

[1]

Anleitung

Alle Permutationen von „1“ sind nur „1“. Daher ist der mit „1“ verbundene Dezimalwert gleich 1.

Eintreten

str = ‘10’

Ausgabe

[1, 2]

Anleitung

Die Anordnung von „10“ ist nur „01“ und „10“, was jeweils 1 und 2 entspricht.

Eintreten

‘101’

Ausgabe

[3, 5, 6]

Anleitung

Alle möglichen Permutationen von „101“ sind „110“, „101“, „110“, „011“, „101“ und „011“. Wenn wir sie in Dezimalzahlen umwandeln, erhalten wir 3, 5 und 6 eindeutige Dezimalzahlen Zahlen.

Methode 1

Bei der ersten Methode verwenden wir Backtracing, um alle Permutationen der Binärzeichenfolge zu erhalten. Danach wandeln wir die binäre Permutation in Dezimalwerte um und verwenden diesen Satz, um den eindeutigen Dezimalwert auszuwählen. Wir werden Dezimalzahlen mithilfe der pow()-Methode und der for-Schleife in Binärzahlen umwandeln.

Algorithmus

• Schritt 1 – Definieren Sie die Funktion „getDecimalPermutations()“, um den resultierenden Dezimalwert zu erhalten.

• Schritt 2 – Führen Sie die Funktion „getBinaryPermutations()“ aus, um alle binären Permutationen der Zeichenfolge abzurufen. Zusätzlich werden Strings, linke und rechte Indizes sowie Permutationsvektoren als Argumente übergeben.

• Schritt 2.1 – Wenn in der Funktion „getBinaryPermutations()“ der linke und der rechte Index gleich sind, schieben Sie die resultierende Zeichenfolge in die permutierte Liste.

• Schritt 2.2 – Wenn der linke und der rechte Index nicht gleich sind, verwenden Sie eine for-Schleife, um die Zeichenfolge vom linken Index zum rechten Index zu iterieren.

• Schritt 2.3 – Vertauschen Sie die Zeichen am i-ten Index und am linken Index in der for-Schleife.

• Schritt 2.4 - Rufen Sie die Funktion „getBinaryPermutations“ erneut mit denselben Parametern und dem Index „left + 1“ auf.

• Schritt 2.5 – Vertauschen Sie die Zeichen am i-ten Index und am linken Index für Backtracking-Zwecke.

• Schritt 3 – Erstellen Sie eine Sammlung mit dem Namen „allDecimals“. Anschließend iterieren Sie über alle Permutationen der Binärzeichenfolge.

• Schritt 4 – Rufen Sie die Funktion bToD() auf, um binär in dezimal umzuwandeln.

• Schritt 4.1 – Initialisieren Sie in der bToD()-Funktion die Dezimalvariable mit dem Wert 0.

• Schritt 4.2 – Verwenden Sie eine for-Schleife, um die Binärzeichenfolge beginnend am Ende zu durchlaufen und fügen Sie „(num[i] – ‚0‘) * pow(2, j )‘ hinzu, um sie in einen Dezimalwert umzuwandeln.

• Schritt 4.3 – Dezimalwert zurückgeben.

• Schritt 5 – Fügen Sie in der Funktion „getDecimalPermutations“ den von der Funktion bToD() zurückgegebenen Dezimalwert ein.

• Schritt 6 – Drucken Sie alle Werte des Satzes aus, der eindeutige Dezimalwerte enthält.

Beispiel

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

Ausgabe

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

• Zeitkomplexität - O(n!). Die Zeitkomplexität der Funktion „getBinaryPermutations()“ beträgt „n!“, da wir Backtracking verwenden, um alle Permutationen zu finden. Die Zeitkomplexität der Funktion bToD() beträgt O(n).

• Raumkomplexität - O(n!) Jeder String hat n!Permutationen, die wir in der Liste speichern.

Methode 2

In dieser Methode verwenden wir anstelle der Backtracking-Methode die Funktion next_permutation() von C++, um die binäre String-Permutation zu generieren. Darüber hinaus haben wir die Methode zur Konvertierung von Binär- in Dezimalzahlen geändert.

Algorithmus

• Schritt 1 - Definieren Sie den Satz „allNumbers“.

• Schritt 2 – Die Methode sort() wird zum Sortieren von Binärzeichenfolgen verwendet.

• Schritt 3 – Verwenden Sie eine Do-While-Schleife, um jede Permutation der Zeichenfolge zu durchlaufen.

• Schritt 4 – Rufen Sie in der do-while-Schleife die Funktion bToD() auf, indem Sie eine Zeichenfolge als Parameter übergeben, um eine Binärzahl in eine Dezimalzahl umzuwandeln.

• Schritt 4.1 - Definieren Sie in der Funktion bToD() die Variable „currentBase“ und initialisieren Sie sie auf 1.

• Schritt 4.2 – Verwenden Sie eine for-Schleife und iterieren Sie die Zeichenfolge ab dem letzten Index.

• Schritt 4.3 – Wenn in der for-Schleife das aktuelle Zeichen gleich „1“ ist, müssen wir den Wert „currentBase“ zur „decimal_number“ hinzufügen.

  < /里>

• Schritt 4.4 – CurrentBase mit 2 multiplizieren.

• Schritt 5 – Fügen Sie die Dezimalzahl in den Satz „allNumber“ ein.

• Schritt 6 – Verwenden Sie die Methode next_permutation() in der Bedingung der do-while-Schleife, da sie „true“ zurückgibt, wenn die nächste Permutation der Zeichenfolge existiert.

• Schritt 7 – Drucken Sie alle in „allNumbers“ hinzugefügten Zahlen aus, um eindeutige Dezimalzahlen zu erhalten, die allen Permutationen der angegebenen Binärzeichenfolge zugeordnet sind.

示例

#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() 方法。

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

Das obige ist der detaillierte Inhalt vonVerschiedene Zahlen, die durch Generieren aller Permutationen einer Binärzeichenfolge erhalten werden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!