Page 1 of 1

10455 - Gray Code

Posted: Mon Apr 12, 2004 8:10 pm
by ..
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!

Posted: Tue Jun 01, 2004 2:56 pm
by 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.

Posted: Wed Apr 18, 2007 3:48 am
by marthapfhui
wyvmak wrote: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.

Posted: Mon Mar 31, 2008 1:12 am
by 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).