Generate all bitstrings of length $n$ with Hamming weight in the interval $[k,l]$ by flipping a single bit or exchanging two bits in each step.
For $k=l$ we obtain
The
Hamming weight of a bitstring is the number of 1s in it.
A natural framework for solving generation problems that involve bitstrings with particular Hamming weights is the
$n$-dimensional hypercube, the graph formed by all bitstrings of length $n$, with an edge between any two bitstrings that differ in a single bit.
All bitstrings with a fixed Hamming weight are referred to as a
level of the hypercube.
Essentially, we consider the subgraph of the $n$-dimensional hypercube induced by all levels in the range $[k,l]$, and we ask for a Hamilton cycle in this graph.
These subgraphs are bipartite, with the partition classes given by all even and odd levels, but unfortunately, the partition classes have different sizes unless $n$ is even and $[k,l]=[0,n]$ or $n$ is odd and $n=k+l$.
So only in those cases can a Hamilton cycle possibly exist.
The paper by Gregor and Mütze [GM18] therefore introduces the following two relaxations of the notion of a Hamilton cycle:
A
saturating cycle is a cycle that visits all vertices in the smaller partition class of the bipartite graph.
A
tight enumeration is a cyclic listing that visits every vertex of the bipartite graph exactly once, and that flips a single bit in most steps (we move along an edge of the graph between the two partitions classes), exchanging two bits only in few steps (we move along a non-edge of the graph inside the bigger partition class), where 'few' means exactly the difference in size between the two partition classes.
If both partition classes of the underlying graph have the same size, which happens exactly in the cases decscribed before, then the two notions are equal to a Hamilton cycle.
The binary reflected Gray code (BRGC) was invented by Frank Gray [Gra53], and it is a simple solution for the case $[k,l]=[0,n]$, i.e., we obtain a single-flip listing of all $2^n$ bitstrings of length $n$ (=Hamilton cycle).
Tang and Liu [TL73] proved that we may restrict the BRGC to any interval $[k,l]$ of levels, by omitting the bitstrings whose Hamming falls outside this range, and obtain a listing which flips exactly two bits at the boundary levels (in fact, a 0-bit is exchanged with a 1-bit).
This trimming technique can therefore be used to construct tight enumerations.
This is illustrated in the following figure for $n=5$ and for different intervals (the BRGC is the left column), where 0=white and 1=black.
The paper by Gregor and Mütze [GM18] proves that moreover, any two such bitstrings at the boundary levels that differ in two bits have a unique common neighbor in the level above and below, and all these neighbors are distinct, so the trimming technique can also be used to construct saturating cycles.
All algorithms running on this website are described in detail in their paper [GM18].
Apart from restricting the weight range, there are also various other sublists of the BRGC that yield interesting Gray codes.