Вы можете создать массив счетчиков для позиций в 1 с в числе и собрать его, сдвинув биты в их соответствующие позиции. Я создал пример ниже. Он работает довольно быстро (меньше 32 секунд на моем ноутбуке):
bitCount = 32
oneCount = 6
maxBit = 1<<(bitCount-1)
ones = [1<<b for b in reversed(range(oneCount)) ] # start with bits on low end
ones[0] >>= 1 # shift back 1st one because it will be incremented at start of loop
index = 0
result = []
while index < len(ones):
ones[index] <<= 1 # shift one at current position
if index == 0:
number = sum(ones) # build output number
result.append(number)
if ones[index] == maxBit:
index += 1 # go to next position when bit reaches max
elif index > 0:
index -= 1 # return to previous position
ones[index] = ones[index+1] # and prepare it to move up (relative to next)
64 бита занимает около минуты, примерно пропорционально количеству выводимых значений. O (п)
Тот же подход можно выразить более кратко в рекурсивной функции генератора, которая позволит более эффективно использовать битовые комбинации:
def genOneBits(bitcount=32,onecount=6):
for bitPos in range(onecount-1,bitcount):
value = 1<<bitPos
if onecount == 1: yield value; continue
for otherBits in genOneBits(bitPos,onecount-1):
yield value + otherBits
result = [ n for n in genOneBits(32,6) ]
Это не быстрее, когда вы получаете все числа, но разрешает частичный доступ к списку, не просматривая все значения.
Если вам нужен прямой доступ к N-ой битовой комбинации (например, для получения случайной однобитовой комбинации), вы можете использовать следующую функцию. Это работает как индексирование списка, но без необходимости генерировать список шаблонов.
def numOneBits(bitcount=32,onecount=6):
def factorial(X): return 1 if X < 2 else X * factorial(X-1)
return factorial(bitcount)//factorial(onecount)//factorial(bitcount-onecount)
def nthOneBits(N,bitcount=32,onecount=6):
if onecount == 1: return 1<<N
bitPos = 0
while bitPos<=bitcount-onecount:
group = numOneBits(bitcount-bitPos-1,onecount-1)
if N < group: break
N -= group
bitPos += 1
if bitPos>bitcount-onecount: return None
result = 1<<bitPos
result |= nthOneBits(N,bitcount-bitPos-1,onecount-1)<<(bitPos+1)
return result
# bit pattern at position 1000:
nthOneBit(1000) # --> 10485799 (00000000101000000000000000100111)
Это позволяет получить битовые комбинации для очень больших целых чисел, которые было бы невозможно сгенерировать полностью:
nthOneBits(10000, bitcount=256, onecount=9)
# 77371252457588066994880639
# 100000000000000000000000000000000001000000000000000000000000000000000000000000001111111
Стоит отметить, что порядок шаблонов не соответствует порядку номеров соответствующих чисел
Хотя nthOneBits () может создавать любой шаблон мгновенно, он намного медленнее других функций при массовом создании шаблонов. Если вам нужно манипулировать ими последовательно, вы должны перейти к функции генератора, а не к циклу nthOneBits ().
Кроме того, достаточно легко настроить генератор, чтобы он запускался по определенному шаблону, чтобы вы могли получить лучшее от обоих подходов.
Наконец, может быть полезно получить следующий битовый шаблон с учетом известного шаблона. Вот что делает следующая функция:
def nextOneBits(N=0,bitcount=32,onecount=6):
if N == 0: return (1<<onecount)-1
bitPositions = []
for pos in range(bitcount):
bit = N%2
N //= 2
if bit==1: bitPositions.insert(0,pos)
index = 0
result = None
while index < onecount:
bitPositions[index] += 1
if bitPositions[index] == bitcount:
index += 1
continue
if index == 0:
result = sum( 1<<bp for bp in bitPositions )
break
if index > 0:
index -= 1
bitPositions[index] = bitPositions[index+1]
return result
nthOneBits(12) #--> 131103 00000000000000100000000000011111
nextOneBits(131103) #--> 262175 00000000000001000000000000011111 5.7ns
nthOneBits(13) #--> 262175 00000000000001000000000000011111 49.2ns
Как и nthOneBits (), этот не требует времени на установку. Его можно использовать в сочетании с nthOneBits () для получения последующих шаблонов после получения исходного в заданной позиции. nextOneBits () намного быстрее, чем nthOneBits (i + 1), но все же медленнее, чем функция генератора.
Для очень больших целых чисел использование nthOneBits () и nextOneBits () может быть единственным практическим вариантом.