Все перестановки подмножества флагов

Question

У меня есть набор бинарных флагов произвольного размера в виде числа int.

Например, число "18" < 2**5 => минимум 5 флагов.

Мне нужно найти все сочетания установленных флагов, по довольно замороченной схеме. Я лучше приведу пример и покажу, что хочу получить. Я хочу написать генератор, который получает на вход число, и возвращает все комбинации ТОЛЬКО установленных бит этого числа*. Например, рассмотрим число 18:

>>> bin(18)
'0b10010'

Я хочу сделать генератор, который будет возвращать следующее:

yield [True, False, False, True, False] # исходное число
yield [False, False, False, True, False] # первый флаг установлен в 'False'
yield [True, False, False, False, False] # только второй флаг установлен в 'False'
yield [False, False, False, False, False] # оба флага установлены в `False`

Изменяться могут только единицы, которые были в исходном числе.
Порядок перебора флагов важен, флаги перебираются слева направо.
Генерируемая последовательность не содержит повторений.
Комбинация, в которой выключено два флага должна идти всегда после любой комбинации, в которой выключен лишь один флаг. То есть

[True, True, False, True]

лучше, чем

[True, False, False, True]

и чем

[True, True, False, False]

Поэтому генератор должен выплюнуть комбинации, которые наиболее близки к исходной последовательности раньше.

Меня устроит, если вместо списка будут возвращаться числа int. Для моего примера:

yield 18
yield 2
yield 16
yield 0

Зачем это нужно? Я ищу наиболее близкую (в метрике Левенштейна (без перестановок соседей)) комбинацию набора исходных данных для обучения нейронной сети для предсказания определённого набора. Флаги - это наличие/отсутствие столбца в исходных данных. Я прогоняю полученное число через предикат, чтобы понять, подойдёт оно мне или нет.

Алгоритм CPU_Bound (требователен к асимптотической сложности).

В итоге, пользуясь ответами @MBo и @Stanislav Volodarskiy, я использовал следующий код (Критика всегда приветствуется!):

from itertools import combinations

def gen_submasks(n:int):
    def gen_bases(n:int):
        while n > 0:
            yield (base := 1 << n.bit_length() - 1)
            n = n ^ base
            
            # alternative syntax:
            # base = 1 << n.bit_length() - 1
            # yield base
            # n ^= base
    
    for count in range(n.bit_count()):
        for combination in combinations(gen_bases(n), count):
            yield n - sum(combination)
    
    yield 0

def main():
    n = 41
    for submask in gen_submasks(n):
        print(bin(submask)[2:].zfill(n.bit_length()))

main()

# 101001
# 001001
# 100001
# 101000
# 000001
# 001000
# 100000
# 000000

Answer 1

Перебор подмасок:

def submasks(mask):
    sub = mask
    while sub:
        yield sub
        sub = (sub-1) & mask

mask = 41 #101001
for s in submasks(mask):
    print(s, bin(s)[2:])

41 101001
40 101000
33 100001
32 100000
9 1001
8 1000
1 1

Answer 2

Выделяем все установленные биты в виде кортежа. Затем перебираем подмножества битов уменьшая их мощность. Подмножество собирается из битов - это нужная нам маска:

def bits(n):
    """ bits of n ascending """
    while n > 0:
        b = n ^ (n & (n - 1))  # least bit of n
        yield b
        n ^= b                 # clear least bit


def masks(n):
    """ n submasks descending bit population, ascending value """
    bs = tuple(bits(n))

    def c_masks(c, i, m):
        if c == 0:
            yield m
        else:
            for j in range(c - 1, i):
                yield from c_masks(c - 1, j, m | bs[j])

    for c in reversed(range(len(bs) + 1)):  # subset cardinality
        yield from c_masks(c, len(bs), 0)


def main():
    n = int(input())
    w = len(f'{n:b}')
    for m in masks(n):
        print(f'{m:0{w}b}')


main()

$ echo 18 | python masks.py
10010
00010
10000
00000

$ echo 19 | python masks.py
10011
00011
10001
10010
00001
00010
10000
00000

БЛОГ НА HUSL

Все перестановки подмножества флагов

Ответы (2 шт):