Generate symmetric chain Gray code

The $n$-dimensional hypercube is the graph that has as vertices all bitstrings of length $n$, with an edge between any two bitstrings that differ in exactly one bit. The Hamming weight of a bitstring is the number of 1s in it, and the $k$-th level of the hypercube is the the set of all bitstrings with Hamming weight $k$. A symmetric chain is a path $x_k,x_{k+1},\ldots,x_{n-k}$, where $x_i$ is from level $i$ for all $i=k,k+1,\ldots,n-k$. A symmetric chain decomposition is a partition of the vertices of the hypercube into symmetric chains. For instance, for $n=3$ a symmetric chain decomposition is given by $\{\{000,100,110,111\},\{001,101\},\{010,011\}\}$.

The fact that the $n$-dimensional hypercube has a symmetric chain decomposition for every $n$ was first proved by de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk [dBvETK51]. Knuth describes this construction under the name of 'Christmas tree pattern' in Section 7.2.1.6 of his book [Knu11]. Interestingly, there are many different ways to describe the same construction, see [Lew72], [Aig73], and [WW77]. Probably the easiest-to-remember explicit rule to describe the chains of this decomposition was given by Greene and Kleitman [GK76] and is based on 'parenthesis matching'. Their construction can be described as follows: For any bitstring $x$, imagine the 0s to be opening brackets, and the 1s to be closing brackets, and match opening and closing brackets in the natural way. Then, to move up the chain containing $x$, flip the leftmost unmatched 0 (opening bracket) to a 1 (closing bracket). Similarly, to move down the chain containing $x$, flip the rightmost unmatched 1 (closing bracket) to a 0 (opening bracket). For instance, for the bitstring $x=11\color{red}{0011}10\color{red}{01}00$, where the matched bits are highlighted, the chain containing $x$ is given by ${*}{*}\color{red}{0011}{*}{*}\color{red}{01}{*}{*}=\{00\color{red}{0011}00\color{red}{01}00,10\color{red}{0011}00\color{red}{01}00,11\color{red}{0011}00\color{red}{01}00,11\color{red}{0011}10\color{red}{01}00,11\color{red}{0011}11\color{red}{01}00,11\color{red}{0011}11\color{red}{01}10,11\color{red}{0011}11\color{red}{01}11\}$, where the $*$s encode the bits that get flipped along the chain. It is easy to see that this rule indeed yields a symmetric chain decomposition. For instance, for $n=2$ we get the chains $\{{*}{*},01\}$, for $n=3$ we get the chains $\{{*}{*}{*},{*}01,01{*}\}$, for $n=4$ we get the chains $\{{*}{*}{*}{*},01{*}{*},0101,{*}{*}01,0011,{*}01{*}\}$. In the graphical output above, 0=white, 1=black, and *=red.

Gregor, Mička, and Mütze [GMM20] showed that the chains of the Greene-Kleitman symmetric chain decomposition can be ordered cyclically so that any two consecutive chains differ only in a single bit at their top or bottom ends, alternatingly. In fact, the chains in the examples for $n=2,3,4$ listed above are given exactly in such a Gray code ordering; see also the picture below on the left for $n=6$. This ordering has the additional property that when viewing the chains as strings over the alphabet $\{0,1,{*}\}$, then any two consecutive chains differ in at most 3 positions; see the picture below on the right for $n=6$. The resulting Gray code in the hypercube has the minimum number of changes of direction from increasing Hamming weight to decreasing Hamming weight, and vice versa. A similar construction of a Hamilton cycle in the cube that can be decomposed into a symmetric chain decomposition was found by Streib and Trotter [ST14]. However, their symmetric chain decomposition is different from the 'canonic' Greene-Kleitman decomposition described above.

The number of chains in a symmetric chain decomposition of the $n$-dimensional hypercube is given by $\binom{n}{\lfloor n/2\rfloor}$, which is OEIS A001405. By Sperner's theorem, this is the number of bitstrings in the middle level of the cube.

[Zipped C++ source code (GNU GPL)]

• [Aig73] M. Aigner. Lexicographic matching in Boolean algebras. J. Combinatorial Theory Ser. B, 14:187–194, 1973.
• [dBvETK51] N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk. On the set of divisors of a number. Nieuw Arch. Wiskunde (2), 23:191–193, 1951.
• [GK76] C. Greene and D. J. Kleitman. Strong versions of Sperner’s theorem. J. Combinatorial Theory Ser. A, 20(1):80–88, 1976.
• [GMM20] P. Gregor, O. Mička, and T. Mütze. On the central levels problem. In 47th International Colloquium on Automata, Languages, and Programming, volume 168 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. 60, 17. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020.
• [Knu11] D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011.
• [Lew72] M. Lewin. Choice mappings of certain classes of finite sets. Math. Z., 124:23–36, 1972.
• [ST14] N. Streib and W. T. Trotter. Hamiltonian cycles and symmetric chains in Boolean lattices. Graphs Combin., 30(6):1565–1586, 2014.
• [WW77] D. E. White and S. G. Williamson. Recursive matching algorithms and linear orders on the subset lattice. J. Combin. Theory Ser. A, 23(2):117–127, 1977.