Как рекурсивно выводить перестановки нулей и единиц заданной длины? - PullRequest
Новая
       10

Как рекурсивно выводить перестановки нулей и единиц заданной длины?

0 голосов
/ 19 ноября 2018

Я пытаюсь распечатать перестановки 0 и 1 рекурсивно в Python.

Я понимаю, что в itertools есть функция перестановок, но мне было интересно, как можно сделать это рекурсивно, например, 

function name is print_01(k) 
    # ...
    print(permutation)
    # ...

... где k - длина каждой перестановки, которая будет напечатана, поэтому, если вы назовете ее print_01(2), результат будет примерно таким:

00
01
10
11

Выход всегда имеет длину k .

Как я могу сделать это рекурсивно, используя print?

Ответы [ 5 ]

0 голосов
/ 19 ноября 2018

Давайте сделаем это просто: 

def print_01(bits, n=0):
    if n.bit_length() <= bits:
        print('{:0{}b}'.format(n, bits))
        print_01(bits, n + 1)

Тип int имеет метод bit_length(), который сообщает вам минимальное количество двоичных символов, необходимое для представления этого числа - мы используем его для контроля. Вложенное форматирование позволяет нам передавать выходную ширину как переменную.

* 1009 USAGE *

>>> print_01(3)
000
001
010
011
100
101
110
111
>>>
0 голосов
/ 19 ноября 2018

Вот простая рекурсивная версия: 

#!/usr/bin/python -E
#string of binary 1s and 0s, all possible combinations for a given length
def swap(string, loc, val):
    newstring = string[:loc]+val+string[loc+1:]
    return newstring
def printperms(string,n):
    length = len(string)
    if n > 0:
       string = swap(string, (length - n), "0")
       printperms(string, (n -1))
       string = swap(string, (length - n), "1")
       printperms(string, (n -1))
    else:
       print(string)


mystring = "000"
length = len(mystring)
printperms(mystring, length)
mystring = mystring+" "
print("############################################")
printperms(mystring,length+1)
0 голосов
/ 19 ноября 2018

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

def print_01(k):
    end = 1<<k   #this is the integer with binary developpement 1 followed by k zeros
    for j in range(end): # iterate until end means getting all k - 0-1 combinations
        comb = bin(j)[2:].zfill(k)
        print [int(x) for x in comb]
0 голосов
/ 19 ноября 2018

Вам действительно нужно переставить ...?Если нет, попробуйте ниже 

def print_01(length):
    for i in range(1 << length):
        print(format(i, '0{}b'.format(length)))


def main():
    '''The Main'''
    print_01(2)
    print_01(3)


if __name__ == '__main__':
    main()
0 голосов
/ 19 ноября 2018

Не выдавая код, я попытаюсь дать подсказки, необходимые для вас, чтобы придумать код.

Идея состоит в том, чтобы сделать рекурсивный вызов, чтобы добавить еще одну цифру к накопленной строке, который изначально является пустым.

Так называемый «базовый случай» рекурсии - это когда накопленная строка имеет желаемую длину.Здесь вы можете вывести его (или сохранить где-нибудь)

Вам понадобится цикл для посещения двух возможных цифр.

Дайте мне знать, достаточно ли этого для начала работы.

Оповещение о спойлере (смотрите только после попытки):

...