Given a binary string S, the task is to print all distinct decimal numbers that can be obtained by generating all permutations of the binary string.
Examples:
Input: S = “110”
Output: {3, 5, 6}
Explanation:
All possible permutations are {“110”, “101”, “110”, “101”, “011”, “011”}.
Equivalent decimal numbers of these binary strings are {6, 5, 6, 5, 3, 3} respectively.
Therefore, the distinct decimal numbers obtained are {3, 5, 6}.Input: S = “1010”
Output: {3, 5, 6, 9, 10, 12}
Approach: The problem can be solved using a Set. Follow the steps below to solve the problem:
- Convert the given string to a list of characters.
- Permute this list using built-in python function itertools. permutations().
- Initialize an empty string s.
- Traverse the list of permutations and perform the following steps for each permutation:
- Iterate over the characters and add them to the string.
- Convert this binary string to equivalent decimal.
- Insert the current decimal value obtained into a set.
- Finally, print the numbers present in the set.
Below is the implementation of the above approach:
C++
#include <iostream>#include <algorithm>#include <set>using namespace std;// Function to convert binary// string to equivalent decimalint binToDec(string n) { string num(n); int dec_value = 0; // Initializing base // value to 1, i.e 2 ^ 0 int base1 = 1; int len1 = num.length(); for (int i = len1 - 1; i >= 0; i--) { if (num[i] == '1') { dec_value += base1; } base1 = base1 * 2; } // Return the resultant // decimal number return dec_value;}// Function to print all distinct// decimals represented by the// all permutations of the stringvoid printDecimal(string permute) { // Set to store distinct // decimal representations set<int> allDecimals; sort(permute.begin(), permute.end()); // Iterate over all permutations do { // Convert the current binary // representation to decimal int result = binToDec(permute); // Add the current decimal // value into the set allDecimals.insert(result); } while (next_permutation(permute.begin(), permute.end())); // Print the distinct decimals for (auto i : allDecimals) cout << i << " "; cout << endl;}// Utility function to print all// distinct decimal representations// of all permutations of stringvoid totalPermutations(string string){ // Function call to print all distinct // decimal values represented by all // permutations of the given string printDecimal(string);}// Given binary stringstring binarystring = "1010";int main() { totalPermutations(binarystring); return 0;}// This code is contributed by phasing17. |
Java
import java.util.*;public class Main { // Function to convert binary string to equivalent decimal static int binToDec(String n) { String num = new String(n); int dec_value = 0; // Initializing base value to 1, i.e 2 ^ 0 int base1 = 1; int len1 = num.length(); for (int i = len1 - 1; i >= 0; i--) { if (num.charAt(i) == '1') { dec_value += base1; } base1 = base1 * 2; } // Return the resultant decimal number return dec_value; } // Function to print all distinct decimals represented by the all permutations of the string static void printDecimal(String permute) { // Set to store distinct decimal representations Set<Integer> allDecimals = new HashSet<Integer>(); char[] charArray = permute.toCharArray(); Arrays.sort(charArray); // Iterate over all permutations do { // Convert the current binary representation to decimal int result = binToDec(new String(charArray)); // Add the current decimal value into the set allDecimals.add(result); } while (nextPermutation(charArray)); // Print the distinct decimals for (int i : allDecimals) { System.out.print(i + " "); } System.out.println(); } // Utility function to print all distinct decimal representations of all permutations of string static void totalPermutations(String str) { // Function call to print all distinct decimal values represented by all permutations of the given string printDecimal(str); } // Given binary string static String binarystring = "1010"; public static void main(String[] args) { totalPermutations(binarystring); } // Function to get the next permutation of a character array static boolean nextPermutation(char[] arr) { int i = arr.length - 2; while (i >= 0 && arr[i] >= arr[i + 1]) { i--; } if (i < 0) { return false; } int j = arr.length - 1; while (arr[j] <= arr[i]) { j--; } swap(arr, i, j); reverse(arr, i + 1, arr.length - 1); return true; } // Function to swap two elements in a character array static void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Function to reverse a portion of a character array static void reverse(char[] arr, int i, int j) { while (i < j) { swap(arr, i, j); i++; j--; } }} |
Python3
# Python3 program for the above approachfrom itertools import permutations# Function to convert binary# string to equivalent decimaldef binToDec(n): num = n dec_value = 0 # Initializing base # value to 1, i.e 2 ^ 0 base1 = 1 len1 = len(num) for i in range(len1 - 1, -1, -1): if (num[i] == '1'): dec_value += base1 base1 = base1 * 2 # Return the resultant # decimal number return dec_value# Function to print all distinct# decimals represented by the# all permutations of the stringdef printDecimal(permute): # Set to store distinct # decimal representations allDecimals = set() # Iterate over all permutations for i in permute: # Initialize an empty string s = "" # Traverse the list for j in i: # Add each element # to the string s += j # Convert the current binary # representation to decimal result = binToDec(s) # Add the current decimal # value into the set allDecimals.add(result) # Print the distinct decimals print(allDecimals) # Utility function to print all# distinct decimal representations# of all permutations of stringdef totalPermutations(string): # Convert string to list lis = list(string) # Built in method to store all # the permutations of the list permutelist = permutations(lis) printDecimal(permutelist)# Given binary stringbinarystring = '1010'# Function call to print all distinct# decimal values represented by all# permutations of the given stringtotalPermutations(binarystring) |
C#
using System;using System.Collections.Generic;using System.Linq;namespace BinaryPermutations {class Program { static void Main(string[] args) { string binaryString = "1010"; TotalPermutations(binaryString); } static int BinToDec(string n) { string num = n; int dec_value = 0; int base1 = 1; int len1 = num.Length; for (int i = len1 - 1; i >= 0; i--) { if (num[i] == '1') { dec_value += base1; } base1 = base1 * 2; } return dec_value; } static void PrintDecimal(string permute) { HashSet<int> allDecimals = new HashSet<int>(); char[] permuteChars = permute.ToCharArray(); Array.Sort(permuteChars); do { int result = BinToDec(new string(permuteChars)); allDecimals.Add(result); } while (NextPermutation(permuteChars)); foreach(int i in allDecimals) { Console.Write(i + " "); } Console.WriteLine(); } static void TotalPermutations(string str) { PrintDecimal(str); } static bool NextPermutation(char[] array) { // Find non-increasing suffix int i = array.Length - 1; while (i > 0 && array[i - 1] >= array[i]) { i--; } if (i <= 0) { return false; } // Find successor to pivot int j = array.Length - 1; while (array[j] <= array[i - 1]) { j--; } char temp = array[i - 1]; array[i - 1] = array[j]; array[j] = temp; // Reverse suffix j = array.Length - 1; while (i < j) { temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } return true; }}}// This code is provided by user_dtewbxkn77n |
Javascript
// JavaScript implementation of above approach// Function to convert binary// string to equivalent decimalfunction binToDec(n) { let num = n; let dec_value = 0; // Initializing base // value to 1, i.e 2 ^ 0 let base1 = 1; let len1 = num.length; for (let i = len1 - 1; i >= 0; i--) { if (num[i] === "1") { dec_value += base1; } base1 = base1 * 2; } // Return the resultant // decimal number return dec_value;}// Function to print all distinct// decimals represented by the// all permutations of the stringfunction printDecimal(permute) { // Set to store distinct // decimal representations let allDecimals = new Set(); // Iterate over all permutations permute.forEach((i) => { // Initialize an empty string let s = ""; // Traverse the list for (let j of i) { // Add each element // to the string s += j; } // Convert the current binary // representation to decimal let result = binToDec(s); // Add the current decimal // value into the set allDecimals.add(result); }); allDecimals = Array.from(allDecimals) allDecimals.sort(function(a, b) { return a - b; }) // Print the distinct decimals console.log(allDecimals);}// Utility function to print all// distinct decimal representations// of all permutations of stringfunction totalPermutations(string) { // Initialize an empty list let lis = string.split(""); // Generate all permutations let permutelist = permute(lis); // Pass the list of permutations // to the printDecimal function printDecimal(permutelist);}// Helper function to generate all permutationsfunction permute(arr) { let result = []; if (arr.length === 1) { return [arr]; } for (let i = 0; i < arr.length; i++) { let current = arr[i]; let remaining = [...arr.slice(0, i), ...arr.slice(i + 1)]; let subpermutes = permute(remaining); for (let j = 0; j < subpermutes.length; j++) { result.push([current, ...subpermutes[j]]); } } return result;}// Given binary stringbinarystring = "1010";// Function call to print all distinct// decimal values represented by all// permutations of the given stringtotalPermutations(binarystring); |
Output:
{3, 5, 6, 9, 10, 12}
Time Complexity: O(N * N!)
Auxiliary Space: O(N * N!)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More Information here on that Topic: geeksforgeeks.org/distinct-numbers-obtained-by-generating-all-permutations-of-a-binary-string/ […]
… [Trackback]
[…] Find More Information here on that Topic: geeksforgeeks.org/distinct-numbers-obtained-by-generating-all-permutations-of-a-binary-string/ […]