Distinct Numbers obtained by generating all permutations of a Binary String

Distinct Numbers obtained by generating all permutations of a Binary String

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:

Below is the implementation of the above approach:

Python3

from itertools import permutations    def binToDec(n):            num = n     dec_value = 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 dec_value    def printDecimal(permute):                      allDecimals = set()                 for i in permute:                             s = ""                             for j in i:                                                    s += j                                          result = binToDec(s)                                      allDecimals.add(result)                  print(allDecimals)        def totalPermutations(string):               lis = list(string)                      permutelist = permutations(lis)            printDecimal(permutelist)       binarystring = '1010'    totalPermutations(binarystring)

Output:

{3, 5, 6, 9, 10, 12}

Time Complexity: O(N * N!)
Auxiliary Space: O(N * N!)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets