|
|
A351939
|
|
Irregular triangle read by rows: the n-th row contains the values 0..2^n-1 sorted first by Hamming weight and then by position in reflected Gray code.
|
|
2
|
|
|
0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 4, 3, 6, 5, 7, 0, 1, 2, 4, 8, 3, 6, 5, 12, 10, 9, 7, 13, 14, 11, 15, 0, 1, 2, 4, 8, 16, 3, 6, 5, 12, 10, 9, 24, 20, 18, 17, 7, 13, 14, 11, 25, 26, 28, 21, 22, 19, 15, 27, 30, 29, 23, 31, 0, 1, 2, 4, 8, 16, 32, 3, 6, 5, 12, 10, 9, 24, 20, 18, 17, 48, 40, 36, 34, 33, 7, 13, 14, 11, 25
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
Values in the range 0..2^n-1 correspond to length n binary vectors. The Hamming weight is the number of 1 bits. Reflected Gray code is described in A003188 and A014550.
Rows can be subdivided into subsequences of vectors having the same Hamming weight. Within each subsequence, adjacent values will differ by 2 bits. For example, the subsequence of length 5 vectors with Hamming weight 2 is 00011, 00110, 00101, 01100, 01010, 01001, 11000, 10100, 10010, 10001 (in decimal 3, 6, 5, 12, 10, 9, 24, 20, 18, 17).
A revolving door algorithm can be used to enumerate values of the same weight in the required order. See Knuth ("Gray codes for combinations", p. 362) for additional information.
|
|
REFERENCES
|
D. Knuth, The art of computer programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011.
F. Ruskey, Combinatorial Generation. Working Version (1j-CSC 425/520), 2003.
|
|
LINKS
|
|
|
FORMULA
|
The n-th row is the concatenation of the subsequences g(n, 0), ..., g(n, n), where the subsequences are defined as follows:
g(n, 0) = (0),
g(n, n) = (2^n - 1),
g(n, k) = g(n-1, k) concatenate (g^r(n-1, k-1) + 2^(n-1)) for 0 < k < n.
In the above, g^r(n-1, k-1) + 2^(n-1) means the 2^(n-1) is added to each member of the subsequence g(n-1, k-1) in reversed order.
|
|
EXAMPLE
|
Triangle T(n,k) begins:
n=0: 0;
n=1: 0, 1;
n=2: 0, 1, 2, 3;
n=3: 0, 1, 2, 4, 3, 6, 5, 7;
n=4: 0, 1, 2, 4, 8, 3, 6, 5, 12, 10, 9, 7, 13, 14, 11, 15;
n=5: 0, 1, 2, 4, 8, 16, 3, 6, 5, 12, 10, 9, 24, 20, 18, 17, 7, 13, 14, 11, 25, 26, 28, 21, 22, 19, 15, 27, 30, 29, 23, 31;
...
For row n = 3, the binary words of length 3 in reflected Gray code order are 000, 001, 011, 010, 110, 111, 101, 100. Arranging these by Hamming weight but otherwise preserving the order gives 000, 001, 010, 100, 011, 110, 101, 111. As decimal numbers these are 0, 1, 2, 4, 3, 6, 5, 7, which is row 3.
|
|
MAPLE
|
b:= proc(n) b(n):= `if`(n<2, n, Bits[Xor](n, b(iquo(n, 2)))) end:
h:= proc(n) h(n):= add(i, i=Bits[Split](n)) end:
T:= n-> sort([$0..2^n-1], (x, y)-> h(x)<h(y) or h(x)=h(y) and b(x)<b(y))[]:
|
|
MATHEMATICA
|
b[n_] := If[n < 2, n, BitXor[n, b[Quotient[n, 2]]]];
h[n_] := DigitCount[n, 2, 1];
T[n_] := SortBy[{h, b}][Range[0, 2^n - 1]];
|
|
PROG
|
(PARI) row(n)=vecsort(vector(2^n, i, i--; bitxor(i, i>>1)), (x, y) -> cmp(hammingweight(x), hammingweight(y)))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|