通过生成二进制字符串的所有排列获得的不同数字

问题陈述

我们给定了长度为 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中文网其他相关文章！