Создание списка бит длины n в Python

Question

Я хочу функцию, которая даст мне все возможные строки указанной длины, которые состоят только из нулей и единиц. Например:

spam(4) 

должен получить меня:

['0110', '0111', '0001', '0011', '0010', '0101', '0100', '1110', '1100', '1101', '1010', '1011', '1001', '1000'] 

Я пытался использовать itertools.permutations для работы. Итак, это то, что я сделал.

def getPerms(n): 
    perms = getCandidates(n) 
    res = [] 
    for i in perms: 
     res.extend(permutations(i)) 
    res = clean(res) 
    return res 

def clean(ar): 
    res = [] 
    for i in ar: 
     temp = "" 
     for j in i: 
      temp += j 
     res.append(temp) 
    return list(set(res)) 

def getCandidates(n): 
    res = [] 
    for i in range(1, n): 
     res.append("1"*i + "0"*(n-i)) 
    return res 

Но это ужасно неэффективно и дает ошибку памяти 10 на входе.

Answer 1

Вы просто хотите сгенерировать бит-строки, очевидно. Вот самый быстрый способ я знаю:

for i in xrange(1, 2**n-1): 
    yield '{:0{n}b}'.format(i, n=n) 

Это создает каждый битовая длины точно n, содержащий по меньшей мере один 1 и один 0.

Пример:

>>> def gen(n): 
...  for i in xrange(1, 2**n-1): 
...   yield '{:0{n}b}'.format(i, n=n) 
... 
>>> list(gen(4)) 
['0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110'] 

Answer 2

Использование itertools.product вместо.

>>> import itertools 
>>> [''.join(i) for i in itertools.product('01', repeat=4)] 
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111'] 

Используя функцию (предполагая, что itertools уже импортирован):

def bitGen(n): 
    return [''.join(i) for i in itertools.product('01', repeat=n)] 

Для больших n S может быть более целесообразным, чтобы вернуть генератор.

def bitGen(n): 
    return (''.join(i) for i in itertools.product('01', repeat=n)) 

# Alternatively: 

def bitGen(n): 
    for i in itertools.product('01', repeat=n): 
     yield ''.join(i) 

Answer 3

В дополнение к отличным ответам выше, если вы хотите продолжать вниз путь, который вы начали, здесь лучше реализация с использованием yield:

from itertools import permutations 

def spam(n): 
    for perm in getPerms(n): 
     print perm, 
    print 

def getPerms(n): 
    for i in getCandidates(n): 
     for perm in set(permutations(i)): 
      yield ''.join(perm) 

def getCandidates(n): 
    for i in range(1, n): 
     res = "1" * i + "0" * (n - i) 
     yield res 

spam(4) 

Answer 4

Или вы могли бы использовать рекурсию .. это имеет дополнительное преимущество в том, способно генерировать любому п битному к щелочному числу

def bitStr(numDig, base): 
if numDig == 0: return [] 
if numDig == 1: return [str(i) for i in range(0,base)] 
return [ digit + bits for digit in bitStr(1, base)for bits in bitStr(numDig - 1, base)] 

печать (bitStr (4, 2))