gray-code - {1,...,n} 的所有 k 个元素子集的格雷码

Question

我正在寻找一种算法，它遍历 n 个元素集的所有 k 个元素子集。我不想显式地生成所有这些子集。

有一种简单的算法可以做到这一点，即按字典顺序对相应的位向量进行排序，然后从当前子集转到下一个子集。

尽管如此，我寻求一种在每一步中只切换 2 位的算法。我读过这样的代码称为“灰色代码”，但我没有找到解决我的问题的算法。

是否有一个直接的实现？

Answer 1

这不会是一个完整的答案，但它也不适合评论。

您需要的与格雷码的关系是镜像。每次格雷码设置一个新位时，其下方的所有位都会从该点向后前进（直到该位被清除或上方的位反转反转）。

要使用您的字典顺序重现这一点，您需要反转每次交换后迭代剩余位的顺序。

您可以将其实现为迭代转换，每次遇到从 1 到 0 的转换时，采用常规排序并反复反转剩余位的顺序。