n 个二进制值的所有组合，与先前的组合相比，只有一个分量发生变化

Question

下面是一个包含 2 个二进制值的所有可能组合的向量：

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

现在，问题是我如何生成一个由 2 个二进制值的相同组合组成的序列，与序列中的前一个相比，每个二进制值只有一个分量发生变化，例如：

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

Answer 1

你这里描述的基本上是一个Gray counter [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 例：

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)]

n 个二进制值的所有组合，与先前的组合相比，只有一个分量发生变化

All combinations of n binary values in an order that just one component changes compared to the prior combination

python

combinations

sequence

gray-code