Recursive problem on binary strings (Python)

Question

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!!

I'm taking a look but one thing I see off hand is for m in Y: M.append("1"+s) should be "1"+m? — user2379875
– user2379875, Commented Apr 11, 2019 at 20:29
@user2379875 That is indeed a silly mistake... xD but it does not fix it completely :( Thank you very much for taking a look :3 — Proto
– Proto, Commented Apr 11, 2019 at 20:33

Zizhen Song · Accepted Answer · 2019-04-11 22:09:01Z

2

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']

edited Apr 11, 2019 at 22:09

answered Apr 11, 2019 at 22:02

Zizhen Song

463 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Proto Over a year ago

You sir, are awesome! Thank you !

Lante Dellarovere · Accepted Answer · 2019-04-11 20:42:17Z

0

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']

answered Apr 11, 2019 at 20:42

Lante Dellarovere

1,8582 gold badges9 silver badges10 bronze badges

1 Comment

Proto Over a year ago

That is a really cool way to do it! Unfortunately I have to do it using recursion :( I don't mind it much tho, thinking about this problem for the past hour is helping me understand the principle more and more

Collectives™ on Stack Overflow

Recursive problem on binary strings (Python)

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related