[math-fun] simple pleasures: subset-lex Gray code
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.]
* Joerg Arndt <arndt@jjj.de> [Jan 30. 2012 13:32]:
[...]
Subset-lex alone can be quite cool, here's for the Catalan restricted growth strings: 1: [ . . . . 1 ] 4 ()()()(()) 1.1.1.11.. 2: [ . . . 1 2 ] 4 ()()((())) 1.1.111... 3: [ . . . 1 1 ] 4 ()()(()()) 1.1.11.1.. 4: [ . . . 1 . ] 3 ()()(())() 1.1.11..1. 5: [ . . 1 . 1 ] 4 ()(())(()) 1.11..11.. 6: [ . . 1 1 2 ] 4 ()(()(())) 1.11.11... 7: [ . . 1 1 1 ] 4 ()(()()()) 1.11.1.1.. 8: [ . . 1 2 3 ] 4 ()(((()))) 1.1111.... 9: [ . . 1 2 2 ] 4 ()((()())) 1.111.1... 10: [ . . 1 2 1 ] 4 ()((())()) 1.111..1.. 11: [ . . 1 2 . ] 3 ()((()))() 1.111...1. 12: [ . . 1 1 . ] 3 ()(()())() 1.11.1..1. 13: [ . . 1 . . ] 2 ()(())()() 1.11..1.1. 14: [ . 1 . . 1 ] 4 (())()(()) 11..1.11.. 15: [ . 1 . 1 2 ] 4 (())((())) 11..111... 16: [ . 1 . 1 1 ] 4 (())(()()) 11..11.1.. 17: [ . 1 . 1 . ] 3 (())(())() 11..11..1. 18: [ . 1 1 . 1 ] 4 (()())(()) 11.1..11.. 19: [ . 1 1 1 2 ] 4 (()()(())) 11.1.11... 20: [ . 1 1 1 1 ] 4 (()()()()) 11.1.1.1.. 21: [ . 1 1 2 3 ] 4 (()((()))) 11.111.... 22: [ . 1 1 2 2 ] 4 (()(()())) 11.11.1... 23: [ . 1 1 2 1 ] 4 (()(())()) 11.11..1.. 24: [ . 1 1 2 . ] 3 (()(()))() 11.11...1. 25: [ . 1 1 1 . ] 3 (()()())() 11.1.1..1. 26: [ . 1 2 . 1 ] 4 ((()))(()) 111...11.. 27: [ . 1 2 1 2 ] 4 ((())(())) 111..11... 28: [ . 1 2 1 1 ] 4 ((())()()) 111..1.1.. 29: [ . 1 2 2 3 ] 4 ((()(()))) 111.11.... 30: [ . 1 2 2 2 ] 4 ((()()())) 111.1.1... 31: [ . 1 2 2 1 ] 4 ((()())()) 111.1..1.. 32: [ . 1 2 3 4 ] 4 ((((())))) 11111..... 33: [ . 1 2 3 3 ] 4 (((()()))) 1111.1.... 34: [ . 1 2 3 2 ] 4 (((())())) 1111..1... 35: [ . 1 2 3 1 ] 4 (((()))()) 1111...1.. 36: [ . 1 2 3 . ] 3 (((())))() 1111....1. 37: [ . 1 2 2 . ] 3 ((()()))() 111.1...1. 38: [ . 1 2 1 . ] 3 ((())())() 111..1..1. 39: [ . 1 2 . . ] 2 ((()))()() 111...1.1. 40: [ . 1 1 . . ] 2 (()())()() 11.1..1.1. 41: [ . 1 . . . ] 1 (())()()() 11..1.1.1. 42: [ . . . . . ] 1 ()()()()() 1.1.1.1.1. Generation (in backward order) is (again) loopless and, at 510M/sec the fastest I know (by a solid margin over the 410M/sec of Aaron Williams fastest (cool-lex) beast). Forward generation is at 408M/sec still very OK. I'll write things up for arxiv.
participants (1)
-
Joerg Arndt