透過產生二進位字串的所有排列所獲得的不同數字

問題陳述

我們給定了長度為 N 的二進位字串 str。我們需要找到該字串的所有排列，將它們轉換為十進制值，並傳回所有唯一的十進制值。

範例

輸入

str = ‘1’

輸出

[1]

說明

「1」的所有排列都只是「1」。因此，與「1」相關的十進制值等於 1。

輸入

str = ‘10’

輸出

[1, 2]

說明

‘10’的排列只有‘01’和‘10’，分別相當於1和2。

輸入

‘101’

輸出

[3, 5, 6]

說明

“101”的所有可能排列是“110”、“101”、“110”、“011”、“101”和“011”，如果我們將它們轉換為十進制數字，我們會得到3、5 ，以及6 個唯一的十進制數。

方法 1

在第一種方法中，我們將使用回溯來取得二進位字串的所有排列。之後，我們將二進制排列轉換為十進制值，並使用該集合選擇唯一的十進制值。我們將使用 pow() 方法和 for 迴圈將十進位轉換為二進位。

演算法

• 第 1 步 - 定義「getDecimalPermutations()」函數以取得結果十進位值。

• 第 2 步 - 執行「getBinaryPermutations()」函數以取得字串的所有二進位排列。另外，也傳遞字串、左右索引和排列向量作為參數。

• 步驟 2.1 - 在「getBinaryPermutations()」函數中，如果左右索引相等，則將結果字串推送到排列清單中。

• 步驟 2.2 - 如果左右索引不相等，則使用 for 迴圈從左索引到右索引迭代字串。

• 步驟 2.3 - 在 for 迴圈中交換第 i 個索引和左側索引處的字元。

• 步驟 2.4 - 再次使用與參數相同的參數和「left 1」索引來呼叫「getBinaryPermutations」函數。

• 步驟 2.5 - 交換第 i 個索引和左側索引處的字元以實現回溯目的。

• 第 3 步 - 建立一個名為「allDecimals」的集合。之後，迭代二進位字串的所有排列。

• 第 4 步 - 呼叫 bToD() 函數將二進位轉換為十進位。

• 步驟 4.1 - 在 bToD() 函數中，以 0 值初始化十進位變數。

• 步驟4.2 - 使用for 循環從末尾開始迭代二進位字串，並添加'(num[i] - '0') * pow(2, j )' 轉換為十進制值。

• 步驟 4.3 - 傳回十進位值。

• 第 5 步 - 在「getDecimalPermutations」函數中，插入從 bToD() 函數傳回的十進位值。

• 第 6 步 - 列印該集合的所有值，其中將包含唯一的十進位值。

範例

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

輸出

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

• 時間複雜度 - O(n!)。 “getBinaryPermutations()”函數的時間複雜度是“n！”，因為我們使用回溯來尋找所有排列。 bToD() 函數的時間複雜度為 O(n)。

• 空間複雜度 - O(n!)。每個字串都有 n!我們儲存在列表中的排列。

方法2

在這個方法中，我們將使用 C 的 next_permutation() 函數來產生二進位字串排列，而不是回溯方法。此外，我們也更改了將二進制轉換為十進制的方法。

演算法

• 第 1 步 - 定義「allNumbers」集合。

• 步驟 2 - sort() 方法用於對二進位字串進行排序。

• 第 3 步 - 使用 do-while 迴圈迭代字串的每個排列。

• 步驟 4 - 在 do-while 迴圈中，透過傳遞字串作為參數來呼叫 bToD() 函數，以將二進位轉換為十進位數字。

• 步驟 4.1 - 在 bToD() 函數中，定義「currentBase」變數並將其初始化為 1。

• 步驟 4.2 - 使用 for 循環，並從最後一個索引開始迭代字串。

• 步驟4.3 - 在for迴圈中，如果目前字元等於'1'，我們需要將currentBase值加到'decimal_number'。

• 步驟 4.4 - 將 currentBase 乘以 2。

• 第 5 步 - 將十進位數插入「allNumber」集中。

• 第 6 步 - 在 do-while 循環的條件下使用 next_permutation() 方法，因為如果字串的下一個排列存在，它將傳回 true。

• 第 7 步 - 列印「allNumbers」中新增的所有數字，以獲得與給定二進位字串的所有排列相關的唯一十進制數。

示例

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

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

以上是透過產生二進位字串的所有排列所獲得的不同數字的詳細內容。更多資訊請關注PHP中文網其他相關文章！