Non-recursive Grey code algorithm understanding

2019-08-13 03:46发布

问题:

This is task from algorithms book.

The thing is that I completely don't know where to start!

Trace the following non-recursive algorithm to generate the binary reflexive
Gray code of order 4. Start with the n-bit string of all 0’s. 
For i = 1, 2, ... 2^n-1, generate the i-th bit string by flipping bit b in the 
previous bit string, where b is the position of the least significant 1 in the 
binary representation of i. 

So I know the Gray code for 1 bit should be 0 1, for 2 00 01 11 10 etc.

Many questions

1) Do I know that for n = 1 I can start of with 0 1?

2) How should I understand "start with the n-bit string of all 0's"?

3) "Previous bit string"? Which string is the "previous"? Previous means from lower n-bit? (for instance for n=2, previous is the one from n=1)?

4) How do I even convert 1-bit strings to 2-bit strings if the only operation there is to flip?

This confuses me a lot. The only "human" method I understand so far is: take sets from lower n-bit, duplicate them, invert the 2nd set, add 0's to every element in 1st set, add 1's do every elements in 2nd set. Done (example: 0 1 -> 0 1 | 0 1 -> 0 1 | 1 0 -> 00 01 | 11 10 -> 11 01 11 10 done.

Thanks for any help

回答1:

The answer to all four your questions is that this algorithm does not start with lower values of n. All strings it generates have the same length, and the i-th (for i = 1, ..., 2n-1) string is generated from the (i-1)-th one.

Here is the fist few steps for n = 4:

Start with G0 = 0000

To generate G1, flip 0-th bit in G0, as 0 is the position of the least significant 1 in the binary representation of 1 = 0001b. G1 = 0001.

To generate G2, flip 1-st bit in G1, as 1 is the position of the least significant 1 in the binary representation of 2 = 0010b. G2 = 0011.

To generate G3, flip 0-th bit in G2, as 0 is the position of the least significant 1 in the binary representation of 3 = 0011b. G3 = 0010.

To generate G4, flip 2-nd bit in G3, as 2 is the position of the least significant 1 in the binary representation of 4 = 0100b. G4 = 0110.

To generate G5, flip 0-th bit in G4, as 0 is the position of the least significant 1 in the binary representation of 5 = 0101b. G5 = 0111.