python - n 个二进制值的所有组合，其顺序是只有一个组件与先前的组合相比发生变化

Question

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

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

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

[(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的情况：

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