Два отдельных подхода предлагаются ниже.
Подход 1: Генератор на основе комбинаций
Один из способов реализовать это - использовать внешний l oop сверх количества битов, и внутренний l oop над позициями битов. Для внутреннего l oop, генератор комбинаций может использоваться для перебора позиций битов включения. Соответствующая последовательность будет начинаться с числа со всеми включенными битами, за которым следуют числа со всеми, кроме одного, бит, за которыми следуют числа со всеми, кроме двух битов, ... и, наконец, в конце 0 (без битов включения ). Комбинация битовых позиций может быть преобразована в число путем суммирования 2^position по позициям битовых битов.
Для варианта использования вопроса элементы последовательности будут использоваться в качестве индексов для обхода по соответствующему списку.
Генераторы комбинаций вращающихся дверей перебирают небольшие наборы элементов, которые нужно менять местами в комбинации при каждом посещении. Такой алгоритм, возможно, можно было бы использовать для уменьшения вычислительных требований подхода, предложенного выше, путем изменения текущего числа на каждой итерации в зависимости от того, какой бит будет включен, а какой - выключен.
Вот реализация в Python, которая не использует подход вращающейся двери, на основе встроенного itertools.combinations Python. В приведенном ниже примере использования функции используется всего восемь битов. Для каждого числа в сгенерированной последовательности выходные данные показывают 1) десятичное представление, 2) двоичное представление и 3) количество включенных битов.
from itertools import combinations
def generator(num_bits):
powers = [2 ** exponent for exponent in range(num_bits - 1, -1, -1)]
for num_on in range(num_bits, -1, -1):
for positions in combinations(range(num_bits), num_on):
yield sum(powers[position] for position in positions)
for x in generator(8):
binary = f'{x:#010b}'
bit_count = binary.count('1')
print(f'{x:03} {binary} {bit_count}')
Выход:
255 0b11111111 8
254 0b11111110 7
253 0b11111101 7
251 0b11111011 7
247 0b11110111 7
239 0b11101111 7
223 0b11011111 7
191 0b10111111 7
127 0b01111111 7
252 0b11111100 6
250 0b11111010 6
249 0b11111001 6
...
006 0b00000110 2
005 0b00000101 2
003 0b00000011 2
128 0b10000000 1
064 0b01000000 1
032 0b00100000 1
016 0b00010000 1
008 0b00001000 1
004 0b00000100 1
002 0b00000010 1
001 0b00000001 1
000 0b00000000 0
Подход 2: упорядоченный список индексов
Альтернативный подход - с использованием большего объема памяти, чем предыдущий метод - заключается в вычислении количества битов включения в каждом числе (где «число» здесь - index), а затем создайте список чисел в порядке убывания их количества включенных битов.
Вот реализация в Python. Для букв от a до z вывод показывает символы, упорядоченные по количеству бит в их индексе, а также индекс каждого символа, его двоичное представление и количество включенных битов. bin(.).count('1') используется для подсчета количества знаков в каждом номере. Проблема 29882 на ошибках. python .org предполагает, что встроенный метод bit_count будет доступен в Python 3.10.
letters = [
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
]
n = len(letters)
bit_counts = [bin(x).count('1') for x in range(n)]
indices_lookup = [[] for _ in range(len(bin(n)) - 2)]
for idx, bit_count in enumerate(bit_counts):
indices_lookup[bit_count].append(idx)
ordered_indices = []
for idxs in reversed(indices_lookup):
ordered_indices.extend(idxs)
for x in ordered_indices:
print(f'{letters[x]} {x:02} {x:#07b}')
Выход:
p 15 0b01111 4
x 23 0b10111 4
h 07 0b00111 3
l 11 0b01011 3
n 13 0b01101 3
o 14 0b01110 3
t 19 0b10011 3
v 21 0b10101 3
w 22 0b10110 3
z 25 0b11001 3
d 03 0b00011 2
f 05 0b00101 2
g 06 0b00110 2
j 09 0b01001 2
k 10 0b01010 2
m 12 0b01100 2
r 17 0b10001 2
s 18 0b10010 2
u 20 0b10100 2
y 24 0b11000 2
b 01 0b00001 1
c 02 0b00010 1
e 04 0b00100 1
i 08 0b01000 1
q 16 0b10000 1
a 00 0b00000 0