Все комбинации из n двоичных значений в порядке изменения только одного компонента по сравнению с предыдущей комбинацией

Question

Ниже приведен вектор со всеми возможными комбинациями двух двоичных значений:

[(1,1),(1,0),(0,1),(0,0)]

Теперь вопрос заключается в том, как я могу сгенерировать последовательность из тех же комбинаций из 2 двоичных значений, в каждом из которых изменен только один компонент по сравнению с предыдущим в последовательности, например:

[(1,0),(1,1),(0,1),(0,0)]

Answer 1

То, что вы описываете здесь, в основном является серым счетчиком [wiki]. Счетчик, двоичный код которого всегда меняет ровно одно значение. Мы можем построить счетчик Грея произвольной длины с помощью следующей процедуры:

def gray_count(n=2):
    d = 0
    lst = 1 << (n-1)
    lbm = 0
    popeven = True
    while lbm < lst:
        yield d
        if popeven:
            d ^= 1
        else:
            lbm = d & ((~d)+1)
            d ^= lbm << 1
        popeven = not popeven

или с меньшим if-cases:

def gray_count(n=2):
    d = 0
    lst = 1 << (n-1)
    lbm = 0
    while lbm < lst:
        yield d
        d ^= 1
        yield d
        lbm = d & ((~d)+1)
        d ^= lbm << 1

Это производит генератор целых чисел. Если мы преобразуем их в двоичные представления, мы получим набор битов, которые каждый раз меняются на один бит:

>>> list(map(bin, gray_count(2)))
['0b0', '0b1', '0b11', '0b10']
>>> list(map(bin, gray_count(3)))
['0b0', '0b1', '0b11', '0b10', '0b110', '0b111', '0b101', '0b100']
>>> list(map(bin, gray_count(4)))
['0b0', '0b1', '0b11', '0b10', '0b110', '0b111', '0b101', '0b100', '0b1100', '0b1101', '0b1111', '0b1110', '0b1010', '0b1011', '0b1001', '0b1000']

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

def to_bin(d, n=None):
    while (d > 0 and n is None) or (n is not None and n > 0):
        yield d&1
        d >>= 1
        n -= 1

Таким образом, мы можем затем преобразовать его в двоичные кортежи с помощью:

>>> list(map(tuple, map(partial(to_bin, n=2), gray_count(2))))
[(0, 0), (1, 0), (1, 1), (0, 1)]
>>> list(map(tuple, map(partial(to_bin, n=3), gray_count(3))))
[(0, 0, 0), (1, 0, 0), (1, 1, 0), (0, 1, 0), (0, 1, 1), (1, 1, 1), (1, 0, 1), (0, 0, 1)]
>>> list(map(tuple, map(partial(to_bin, n=4), gray_count(4))))
[(0, 0, 0, 0), (1, 0, 0, 0), (1, 1, 0, 0), (0, 1, 0, 0), (0, 1, 1, 0), (1, 1, 1, 0), (1, 0, 1, 0), (0, 0, 1, 0), (0, 0, 1, 1), (1, 0, 1, 1), (1, 1, 1, 1), (0, 1, 1, 1), (0, 1, 0, 1), (1, 1, 0, 1), (1, 0, 0, 1), (0, 0, 0, 1)]