10455 - Gray Code

[..]

Copied from the problem:

# 1st n-bit gray code has its leftmost bit fixed and it uses 1st (n-1)-bit gray code for upper half and also 1st (n-1)-bit gray code for lower half.
# G(n-1)'th n-bit gray code has its leftmost bit fixed and it uses 1st (n-1)-bit gray code for upper half and G(n-1)'th (n-1)-bit gray code for lower half.
# [G(n-1)+1]'th n-bit gray code has its leftmost bit fixed and it uses 2nd (n-1)-bit gray code for upper half and 1st (n-1)-bit gray code for lower half.
# G(n)'th n-bit gray code has its rightmost bit fixed and it uses G(n-1)'th (n-1)-bit gray code for both halves.

I am not sure if I get the correct meaning of these sentences.....
Does "upper half" means first 2^(n-1) rows?

As I understand, for any n-bit gray code, it should have its leftmost(or rightmost) bit fixed for first 2^(n-1) rows, but it doesn't hold in the sample input:

Code: Select all

111 5

sample output:

Code: Select all

111
110
010
011
001
000
100
101

Could anyone kindly explain to me? Thanks!

[wyvmak]

After someone taught me, I've the following interpretation:

G(n) represents the number of ways to form the n-bit gray code.

For n-bit, you can fix 1st bit, 2nd bit, ..., n-th bit.
After each bit fixed, you can have G(n-1) ways to generate the upper half, and G(n-1) ways to generate the lower half.

Index is the i-th way to generate n-bit gray code according the description...

Maybe I 'm not stating clear enough. Hope this helps.

[marthapfhui]

After someone taught me, I've the following For n-bit, you can fix 1st bit, 2nd bit, ..., n-th bit.
After each bit fixed, you can have G(n-1) ways to generate the upper half, and G(n-1) ways to generate the lower half.

I have no idea on the meaning of "upper half" and "lower half". What do these terms mean?

Thanks a lot.

[Stefan_Bialucha]

upper half is the block of first half count of rows (in the sample output above: half of 8 rows = 4) and
lower half accordingly the remaining block of the same size (in the sample output above: last 4 rows).