Каков наилучший способ [лучшая временная сложность] для создания всех двоичных масок заданной длины в Python3?

Я хочу сгенерировать все двоичные маски заданной длины, т.е. для n = 3 я хотел бы сгенерировать 000, 001, 010, 011, 100, 101, 110, 111.

Мой текущий код выглядит примерно так, довольно старый стиль, не могу понять, как сделать то же самое с f-строками или чем-то классным вместо zfill.

for i in range(2**n):
    print(bin(i)[2:].zfill(n))

Есть идеи? Спасибо!


python-3.x bit-manipulation bitmask
person tkrishtop    schedule 25.12.2019    source источник
comment
@BobJarvis-ReinstateMonica, вопрос был о производительности. Здесь я трачу n log(n) на преобразование в двоичное число, а затем на zfill для каждого числа, в сумме получается n log(n) 2^n. Интересно, можно ли это сделать быстрее. В идеале 2^n.   -  person tkrishtop    schedule 26.12.2019

Ответы (2)


arrow_upward
3
arrow_downward

Вы можете повысить эффективность существующего кода, используя диапазон от 2**n до 2**(n+1) и взяв подстроку из еще одного символа. Это устраняет необходимость заполнения нулями:

n = 3
for i in range(2**n, 2**(n+1)):
     print(bin(i)[3:])

Выход

000
001
010
011
100
101
110
111
person Nick    schedule 26.12.2019

arrow_upward
-1
arrow_downward

Вы можете сделать это с помощью itertools.

from itertools import product

for t in product(('0', '1',), repeat=3):
    print(''.join(t))

Сложность вызова product() равна O(1), потому что это генератор, поэтому ничего не происходит, пока вы не выполните итерацию.

Сложность фактической функции product() обсуждается здесь: эффективность Python itertools.product()

person blueteeth    schedule 26.12.2019
comment
Но запуск цикла — это не O(1), потому что на самом деле работает генератор... - person Mad Physicist; 26.12.2019