CODEWITHSUNDEEP
pythonrecursion
Proto
Proto

Reputation: 71

Recursive problem on binary strings (Python)

I am having issues with this python problem; I have been working for the past hour on it and I am completely stuck.. I am still not very confortable with recursion and the problems keep getting harder, so any type of help is very much appreciated!

The problem is simple, I need to write a function that takes as inputs n and w; where n is the size of the bit string and w is the number of ones in a string. The output should be all of its permutations.

Example:

n = 3, w = 1 : ['001', '010', '100']

n = 4, w = 2: ['0011', '0101', '0110', '1001', '1010', '1100']

This is what I have written so far but as much as I tweak it or run it in python visualizer I just can't figure it out: 

def genBinStr2(n,w):
    if n <=0 or w <= 0 :
        return [""]
    X = genBinStr2(n-1,w)
    Y = genBinStr2(n-1,w-1)
    M = []
    for s in X:
        M.append("0"+s)
    for m in Y:
        M.append("1"+s)
    return M
print (genBinStr2(3,1))

And the output is:

runfile('/Users/Rayan/Desktop/AUB Spring 2019/EECE 230 /Revision/untitled0.py', wdir='/Users/Rayan/Desktop/AUB Spring 2019/EECE 230 /Revision')
['000', '001', '011', '111']

Again any help is appreciated! I really want to be able to solve this

Thank you!!

Upvotes: 0

Views: 896

Answers (2)

Zizhen Song
Zizhen Song

Reputation: 46

Your opening statement does not allow for situation in which w = 0.

For example: print (genBinStr2(3,0)) would return [''] instead of ["000"]

There is also an issue of returning results where the number of 1's is less than w

Here is my solution to the problem using recursion:

def genBinStr2(n,w):
    if n == 1:
        if w == 1:
            return["1"]
        if w == 0:
            return["0"]
    if n <= 0 or w < 0:
        return [""]
    X = genBinStr2(n-1,w)
    Y = genBinStr2(n-1,w-1)
    M = []
    if w < n:
        for s in X:
            M.append("0"+s)
    if w >=1:
        for m in Y:
            M.append("1"+m)
    return M

output:

>>> print (genBinStr2(3,2))
['011', '101', '110']
>>> print (genBinStr2(3,1))
['001', '010', '100']
>>> print (genBinStr2(4,3))
['0111', '1011', '1101', '1110']

Upvotes: 2

Lante Dellarovere
Lante Dellarovere

Reputation: 1858

If you don't mind not using recursion, here a solution with itertools

from itertools import combinations

def ones(n, w):
    combos = [dict.fromkeys(x, "1") for x in combinations(range(n), w)]
    return ["".join([x.get(i, "0") for i in range(n)]) for x in combos]

ones(4, 2)

Output:

['1100', '1010', '1001', '0110', '0101', '0011']

Upvotes: 0

Related Questions