Distinct Numbers obtained by generating all permutations of a Binary String

0 0 7 minutes read

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 decimal
int 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 string
void 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 string
void totalPermutations(string string)
{
   
  // Function call to print all distinct
  // decimal values represented by all
  // permutations of the given string
  printDecimal(string);
}
 
// Given binary  string
string 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 approach
 
from itertools import permutations
 
# Function to convert binary
# string to equivalent decimal
def 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 string
def 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 string
def 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  string
binarystring = '1010'
 
# Function call to print all distinct
# decimal values represented by all
# permutations of the given string
totalPermutations(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 decimal
function 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 string
function 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 string
function 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 permutations
function 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  string
binarystring = "1010";
 
// Function call to print all distinct
// decimal values represented by all
// permutations of the given string
totalPermutations(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 zambiatek!