Рекурсивная функция двоичных строк

Question

Как написать рекурсивную функцию, которая генерирует список двоичных файлов длины n с указанным числом 1 с?Вот код, который рекурсивно генерирует список двоичных файлов;без заданного числа 1 с:

def generateAllBinaryStrings(n, arr, i):  

    if i == n: 
        printTheArray(arr, n)  
        return

    # First assign "0" at ith position  
    # and try for all other permutations  
    # for remaining positions  
    arr[i] = 0
    generateAllBinaryStrings(n, arr, i + 1)  

    # And then assign "1" at ith position  
    # and try for all other permutations  
    # for remaining positions  
    arr[i] = 1
    generateAllBinaryStrings(n, arr, i + 1)  

Взято с гиксфоргеекс

Answer 1

Вы должны сгенерировать все возможные последовательности с добавлением 0 или 1 в каждой позиции. Всего возможных последовательностей = 2 ^ MAX. Следите за количеством единиц в текущей последовательности до тех пор, пока они не прервутся.

# Generate all binary numbers with exactly "n" 1s
# Max digits in the binary number = MAX

def binary(n):
    MAX = 5
    all_solutions = []
    def solve(current, remaining_ones):
        if len(current) > MAX:
            return
        if remaining_ones == 0:
            all_solutions.append(current+"0"*(MAX-len(current)))
            return

        solve(current+"1", remaining_ones - 1)
        solve(current+"0", remaining_ones)

    solve("", n)
    return all_solutions

 print(binary(2))
 # ['11000', '10100', '10010', '10001', '01100', '01010', '01001', '00110', '00101', '00011']

Answer 2

Вы можете сделать это так:

def binaryStrings(n, ones):  
    if n < ones: # impossible
        return []
    if n == ones:
        return ["1" * ones]
    if ones == 0:
        return ["0" * n]
    a = binaryStrings(n-1, ones)
    b = binaryStrings(n-1, ones-1)
    return ["0"+s for s in a] + ["1"+s for s in b]

Пример вызова для получения всех 6-значных двоичных чисел, которые имеют ровно 4 1-значные цифры:

print(binaryStrings(6,4))