Блог

У меня возникли проблемы с этой проблемой python; Я работал над ней в течение последнего часа, и я полностью застрял.. Я все еще не очень доволен рекурсией, и проблемы становятся все сложнее, поэтому любая помощь очень ценится!

Проблема проста, мне нужно написать функцию, которая принимает в качестве входных данных n и w; где n — размер битовой строки, а w — количество единиц в строке. На выходе должны быть все его перестановки.

Пример:

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

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

Это то, что я написал до сих пор, но как бы я ни настраивал его или запускал в python visualizer, я просто не могу понять это:

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

И результат:

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

Опять же, любая помощь приветствуется! Я действительно хочу иметь возможность решить это

Спасибо!!

Ваше вступительное заявление не допускает ситуации, в которой w = 0.

Например: print (genBinStr2(3,0)) вернет [«] вместо [«000»]

Существует также проблема возврата результатов, в которых число единиц меньше w

Вот мое решение проблемы с использованием рекурсии:

 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
  

вывод:

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

Если вы не возражаете не использовать рекурсию, вот решение с 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)
  

Вывод:

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