Gray code for all k element subset of {1,…,n}

问题:

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.

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?

回答1:

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.

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.