{1，...，n}的所有k个元素子集的格雷码 [英] Gray code for all k element subset of {1,...,n}

问题描述

我正在寻找一种迭代n个元素集的所有k个元素子集的算法.我不想显式地生成所有这些子集.

I am seeking for an algorithm which iterates through all k element subsets of an n element set. I do not want to generate all those subset explicitly.

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

There is an easy algorithm to do this, namely sorting the corresponding bit vectors lexographically and then go from the current subset to the next one.

尽管如此，我仍在寻找一种算法，该算法在每个步骤中仅切换2位.我已经读过这样的代码称为灰色代码"，但是我没有找到解决我的问题的算法.

Nevertheless, I seek for an algorithm which only switches 2 bits in each step. I have read that such a code is a called "gray-code" but I did not found an algorithm for my problem.

是否有直接的实现方法?

Is there a straight forward implementation for this?

推荐答案

这不会是一个完整的答案，但也不会包含在注释中.

This isn't going to be a complete answer, but it's also not going to fit in a comment.

与格雷码的关系就是您所需要的镜像.每次格雷码设置一个新位时，它下面的所有位都从该点开始向后向后前进(直到该位被清除或高于该位使反向反转为止).

The relationship to gray code that you need is the mirroring. Every time gray code sets a new bit, all the bits below it progress backwards from that point on (until that bit is cleared or a bit above that reverses the reversal).

要按照字典顺序重现此顺序，您需要反转每次交换后对其余位进行迭代的顺序.

To reproduce this with your lexicographic ordering you need to invert the order in which you iterate through the remaining bits after each swap.

您也许可以将其实现为迭代转换，以常规顺序进行，并在每次遇到从1到0的转换时重复反转其余位的顺序.

You might be able to implement this as an iterative transformation, taking your regular ordering and repeatedly reversing the order of the remaining bits every time you encounter a transition from 1 to 0.

这篇关于{1，...，n}的所有k个元素子集的格雷码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！