From the department of ASCII entertainment: a binary Gray code you have not seen before. Dots for zeros to make the structure more visible.
n: Gray code transition 0: [ . . . . . . ] ---- 1: [ 1 . . . . . ] 1..... 2: [ 1 1 . . . . ] .1.... 3: [ 1 1 1 . . . ] ..1... 4: [ 1 1 1 1 . . ] ...1.. 5: [ 1 1 1 1 1 . ] ....1. 6: [ 1 1 1 1 1 1 ] .....1 7: [ 1 1 1 1 . 1 ] ....1. 8: [ 1 1 1 . . 1 ] ...1.. 9: [ 1 1 1 . 1 1 ] ....1. 10: [ 1 1 1 . 1 . ] .....1 11: [ 1 1 . . 1 . ] ..1... 12: [ 1 1 . . 1 1 ] .....1 13: [ 1 1 . . . 1 ] ....1. 14: [ 1 1 . 1 . 1 ] ...1.. 15: [ 1 1 . 1 1 1 ] ....1. 16: [ 1 1 . 1 1 . ] .....1 17: [ 1 1 . 1 . . ] ....1. 18: [ 1 . . 1 . . ] .1.... 19: [ 1 . . 1 1 . ] ....1. 20: [ 1 . . 1 1 1 ] .....1 21: [ 1 . . 1 . 1 ] ....1. 22: [ 1 . . . . 1 ] ...1.. 23: [ 1 . . . 1 1 ] ....1. 24: [ 1 . . . 1 . ] .....1 25: [ 1 . 1 . 1 . ] ..1... 26: [ 1 . 1 . 1 1 ] .....1 27: [ 1 . 1 . . 1 ] ....1. 28: [ 1 . 1 1 . 1 ] ...1.. 29: [ 1 . 1 1 1 1 ] ....1. 30: [ 1 . 1 1 1 . ] .....1 31: [ 1 . 1 1 . . ] ....1. 32: [ 1 . 1 . . . ] ...1.. 33: [ . . 1 . . . ] 1..... 34: [ . . 1 1 . . ] ...1.. 35: [ . . 1 1 1 . ] ....1. 36: [ . . 1 1 1 1 ] .....1 37: [ . . 1 1 . 1 ] ....1. 38: [ . . 1 . . 1 ] ...1.. 39: [ . . 1 . 1 1 ] ....1. 40: [ . . 1 . 1 . ] .....1 41: [ . . . . 1 . ] ..1... 42: [ . . . . 1 1 ] .....1 43: [ . . . . . 1 ] ....1. 44: [ . . . 1 . 1 ] ...1.. 45: [ . . . 1 1 1 ] ....1. 46: [ . . . 1 1 . ] .....1 47: [ . . . 1 . . ] ....1. 48: [ . 1 . 1 . . ] .1.... 49: [ . 1 . 1 1 . ] ....1. 50: [ . 1 . 1 1 1 ] .....1 51: [ . 1 . 1 . 1 ] ....1. 52: [ . 1 . . . 1 ] ...1.. 53: [ . 1 . . 1 1 ] ....1. 54: [ . 1 . . 1 . ] .....1 55: [ . 1 1 . 1 . ] ..1... 56: [ . 1 1 . 1 1 ] .....1 57: [ . 1 1 . . 1 ] ....1. 58: [ . 1 1 1 . 1 ] ...1.. 59: [ . 1 1 1 1 1 ] ....1. 60: [ . 1 1 1 1 . ] .....1 61: [ . 1 1 1 . . ] ....1. 62: [ . 1 1 . . . ] ...1.. 63: [ . 1 . . . . ] ..1... Note successive transitions are either adjacent (one-close) or three-close. Guessing the recursion may be a fun task (there is a twist wrt. to the "well known" recursions). Hint: this Gray code is to (subset-lex)... n: delta-set subset 0: ..... { } 1: 1.... { 0 } 2: 11... { 0, 1 } 3: 111.. { 0, 1, 2 } 4: 1111. { 0, 1, 2, 3 } 5: 11111 { 0, 1, 2, 3, 4 } 6: 111.1 { 0, 1, 2, 4 } 7: 11.1. { 0, 1, 3 } 8: 11.11 { 0, 1, 3, 4 } 9: 11..1 { 0, 1, 4 } 10: 1.1.. { 0, 2 } 11: 1.11. { 0, 2, 3 } 12: 1.111 { 0, 2, 3, 4 } 13: 1.1.1 { 0, 2, 4 } 14: 1..1. { 0, 3 } 15: 1..11 { 0, 3, 4 } 16: 1...1 { 0, 4 } 17: .1... { 1 } 18: .11.. { 1, 2 } 19: .111. { 1, 2, 3 } 20: .1111 { 1, 2, 3, 4 } 21: .11.1 { 1, 2, 4 } 22: .1.1. { 1, 3 } 23: .1.11 { 1, 3, 4 } 24: .1..1 { 1, 4 } 25: ..1.. { 2 } 26: ..11. { 2, 3 } 27: ..111 { 2, 3, 4 } 28: ..1.1 { 2, 4 } 29: ...1. { 3 } 30: ...11 { 3, 4 } 31: ....1 { 4 } .. what the usual (binary reflected) Gray code ist to binary numbers in counting order. Can be generalized to mixed radix numbers (and for even radices >=4 the transitions are either adjacent or two-close) and a loopless algorithm that does _not_ use any sort of focus pointers can be obtained (which is actually very fast). One-close binary Gray codes exist for n<=6 but not for n=7 (and apparently not for any n>=8). Finding a construction for two-close binary Gray code would be _very_ neat. ...and subset-lex gives fast (loopless) methods for generating non-adjacent forms, here is the Fibonacci case: 0: ........ = { } 1: 1....... = { 0 } 2: 1.1..... = { 0, 2 } 3: 1.1.1... = { 0, 2, 4 } 4: 1.1.1.1. = { 0, 2, 4, 6 } 5: 1.1.1..1 = { 0, 2, 4, 7 } 6: 1.1..1.. = { 0, 2, 5 } 7: 1.1..1.1 = { 0, 2, 5, 7 } 8: 1.1...1. = { 0, 2, 6 } 9: 1.1....1 = { 0, 2, 7 } 10: 1..1.... = { 0, 3 } 11: 1..1.1.. = { 0, 3, 5 } 12: 1..1.1.1 = { 0, 3, 5, 7 } 13: 1..1..1. = { 0, 3, 6 } 14: 1..1...1 = { 0, 3, 7 } 15: 1...1... = { 0, 4 } 16: 1...1.1. = { 0, 4, 6 } 17: 1...1..1 = { 0, 4, 7 } 18: 1....1.. = { 0, 5 } 19: 1....1.1 = { 0, 5, 7 } 20: 1.....1. = { 0, 6 } 21: 1......1 = { 0, 7 } 22: .1...... = { 1 } 23: .1.1.... = { 1, 3 } 24: .1.1.1.. = { 1, 3, 5 } 25: .1.1.1.1 = { 1, 3, 5, 7 } 26: .1.1..1. = { 1, 3, 6 } 27: .1.1...1 = { 1, 3, 7 } 28: .1..1... = { 1, 4 } 29: .1..1.1. = { 1, 4, 6 } 30: .1..1..1 = { 1, 4, 7 } 31: .1...1.. = { 1, 5 } 32: .1...1.1 = { 1, 5, 7 } 33: .1....1. = { 1, 6 } 34: .1.....1 = { 1, 7 } 35: ..1..... = { 2 } 36: ..1.1... = { 2, 4 } 37: ..1.1.1. = { 2, 4, 6 } 38: ..1.1..1 = { 2, 4, 7 } 39: ..1..1.. = { 2, 5 } 40: ..1..1.1 = { 2, 5, 7 } 41: ..1...1. = { 2, 6 } 42: ..1....1 = { 2, 7 } 43: ...1.... = { 3 } 44: ...1.1.. = { 3, 5 } 45: ...1.1.1 = { 3, 5, 7 } 46: ...1..1. = { 3, 6 } 47: ...1...1 = { 3, 7 } 48: ....1... = { 4 } 49: ....1.1. = { 4, 6 } 50: ....1..1 = { 4, 7 } 51: .....1.. = { 5 } 52: .....1.1 = { 5, 7 } 53: ......1. = { 6 } 54: .......1 = { 7 } Generating the list in reverse order can be done via... ulong prev_lexrev_fib(ulong x) // Return previous Fibonacci word in subset-lex order. // Start with zero to generate all words of length n. { ulong x0 = x & -x; // lowest bit if ( x & (x0<<2) ) // easy case: next higher bit is set { x ^= x0; // clear lowest bit return x; } else { x += x0; // move lowest bit to the left x |= (x0!=1); // and set rightmost bit unless blocked by next bit return x; } } ...which, ladies and gentlemen, ist werry beautiful! [He bows and leaves the stage. Deafening silence in the audience.]