n个项目的k组成，带有“灰色代码”类似属性

Question

我已经知道如何产生n个值的k组合，如下所述 >。问题是我需要一个额外的属性：我希望每对连续组合仅在一个位置上有所不同（或“ 灰色代码”类似属性）。在施工期间完成或在生成所有组合后使用特殊排序规则都没关系。

例如，具有k = 3，n = 5的原始实现会产生以下序列

 0 1 2
 0 1 3 <- good, previous line differs only in the last position (2->3)
 0 1 4
 0 2 3 <- bad, there are two changes (1->2) and (4->3)
 0 2 4
 0 3 4
 1 2 3
 1 2 4
 1 3 4
 2 3 4

，我想看到类似的东西（可以有多个满足“灰色代码”类似属性的解决方案）。

 0 1 2
 0 1 3 
 0 2 3
 0 2 4
 0 1 4
 0 3 4
 2 3 4
 1 3 4
 1 2 4
 1 2 3

似乎可以将所有数字保存在组合中（1 0 2不应该发生，只有0 1 2）。

---

更新

答案 @Stef显示了一个解决方案，其中包含以下数字的顺序。如果我们独立考虑不同列中的更改，则无法满足单个变更属性。

0, 1, 2
0, 2, 3
1, 2, 3
0, 1, 3 <- bad, change 1: (1->0), change 2: (2->1)
0, 3, 4
1, 3, 4
2, 3, 4
0, 2, 4
1, 2, 4
0, 1, 4

在组合中重新排序数字的明显建议（0 1 3 1 0 3 ）无法满足上述分类要求。

目前尚不清楚是否存在满足此约束的解决方案的任何对（n，k），但到目前为止，我还没有发现何时无法进行。

Answer 1

我找到了以下复发公式，以生成灰色代码的组合列表：

C(n,k) = C(n-1,k).0 + [C(n-1,k-1)]bar.1

来源： encyclopediaofmaths.org：灰色代码#combinations

带有符号的说明：

• c（n，k）是灰色n元素的k组合列表代码顺序；
• c（n-1，k）.0只是c（n-1，k）
• [l] bar表示“列表l in反向顺序“
• l.1表示“列表L中的元组，n-1添加到每个元组中”，

并使用所有元组，并且使用Python Generrence公式将变为：

def combinations_graycode(n, k):
    yield from combinations_graycode(n-1, k)
    for comb in reversed(list(combinations_graycode(n-1, k-1))):
        yield comb + (n-1,)

添加base--递归的情况，这是整个Python代码：

def combinations_graycode(n, k):
    if k < 0:
        raise ValueError('k must be non-negative')
    elif k > n or n < 1:
        pass
    elif k == 0:
        yield ()
    elif k == n:
        yield tuple(range(n))
    else:
        yield from combinations_graycode(n-1, k)
        for comb in reversed(list(combinations_graycode(n-1, k-1))):
            yield comb + (n-1,)

print(list(combinations_graycode(5, 3)))
# [(0, 1, 2), (0, 2, 3), (1, 2, 3), (0, 1, 3), (0, 3, 4), (1, 3, 4), (2, 3, 4), (0, 2, 4), (1, 2, 4), (0, 1, 4)]