Different numbers obtained by generating all permutations of a binary string

Problem Statement

We are given a binary string str of length N. We need to find all permutations of this string, convert them to decimal values, and return all unique decimal values.

Example

enter

str = ‘1’

Output

[1]

illustrate

All permutations of "1" are just "1". Therefore, the decimal value associated with "1" is equal to 1.

enter

str = ‘10’

Output

[1, 2]

illustrate

The arrangement of '10' is only '01' and '10', which are equivalent to 1 and 2 respectively.

enter

‘101’

Output

[3, 5, 6]

illustrate

All possible permutations of "101" are "110", "101", "110", "011", "101" and "011", if we convert them to decimal numbers we get 3, 5 , and 6 unique decimal numbers.

method 1

In the first method, we will use backtracking to get all permutations of the binary string. After that, we convert the binary permutation into decimal values ​​and use this set to select the unique decimal value. We will convert decimal to binary using pow() method and for loop.

algorithm

• Step 1 - Define the "getDecimalPermutations()" function to get the resulting decimal value.

• Step 2 - Execute the "getBinaryPermutations()" function to get all binary permutations of the string. Additionally, strings, left and right indexes, and permutation vectors are passed as arguments.

• Step 2.1 - In the "getBinaryPermutations()" function, if the left and right indexes are equal, push the resulting string into the permuted list.

• Step 2.2 - If the left and right indices are not equal, use a for loop to iterate the string from the left index to the right index.

• Step 2.3 - Swap the characters at the i-th index and the left index in the for loop.

• Step 2.4 - Call the "getBinaryPermutations" function again with the same arguments and "left 1" index.

• Step 2.5 - Swap the characters at the i-th index and the left index for backtracking purposes.

• Step 3 - Create a collection called "allDecimals". After that, iterate over all permutations of the binary string.

• Step 4 - Call the bToD() function to convert binary to decimal.

• Step 4.1 - In the bToD() function, initialize the decimal variable with a value of 0.

• Step 4.2 - Use for loop to iterate the binary string starting from the end and add '(num[i] - '0') * pow(2, j )' to convert to decimal value.

• Step 4.3 - Return decimal value.

• Step 5 - In the "getDecimalPermutations" function, insert the decimal value returned from the bToD() function.

• Step 6 - Print all values ​​of the set, which will contain unique decimal values.

Example

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

Output

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

• Time complexity - O(n!). The time complexity of the "getBinaryPermutations()" function is "n!" because we use backtracking to find all permutations. The time complexity of the bToD() function is O(n).

• Space complexity - O(n!). Each string has n!permutations that we store in the list.

Method 2

In this approach, we will use C's next_permutation() function to generate binary string permutations instead of the backtracking method. Additionally, we changed the method of converting binary to decimal.

algorithm

• Step 1 - Define the "allNumbers" set.

• Step 2 - The sort() method is used to sort binary strings.

• Step 3 - Use a do-while loop to iterate over each permutation of the string.

• Step 4 - In the do-while loop, call the bToD() function by passing a string as argument to convert binary to decimal number.

• Step 4.1 - In the bToD() function, define the "currentBase" variable and initialize it to 1.

• Step 4.2 - Use a for loop and iterate the string starting from the last index.

• Step 4.3 - In the for loop, if the current character is equal to '1', we need to add the currentBase value to 'decimal_number'.

• Step 4.4 - Multiply currentBase by 2.

• Step 5 - Insert the decimal number into the "allNumber" set.

• Step 6 - Use the next_permutation() method in the condition of the do-while loop because it will return true if the next permutation of the string exists.

• Step 7 - Print all numbers added in "allNumbers" to get unique decimal numbers associated with all permutations of the given binary string.

示例

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

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

The above is the detailed content of Different numbers obtained by generating all permutations of a binary string. For more information, please follow other related articles on the PHP Chinese website!