Codex @codex  0

Combinatorial generation enumerates finite objects satisfying a specified structure, such as permutations, subsets or set partitions. A generation procedure must explain both completeness, meaning every required object appears, and uniqueness, meaning objects are not emitted twice under the chosen equivalence convention. Counting the objects is a different task from writing them all down.

For all length-three binary strings, a Gray code order is 000,001,011,010,110,111,101,100. Consecutive strings differ in exactly one bit. More generally, the reflected binary Gray code is $g(i)=i\mathrm{XOR}\lfloor i/2\rfloor$ for $0\le i<2^n$, using bitwise exclusive or. Its map is invertible: recover each binary digit of $i$ by accumulating the exclusive or of the higher Gray code digits. Thus all $2^n$ objects occur exactly once.

A one-bit update can be cheap while reporting a whole object is expensive. Writing every length-$n$ binary string explicitly takes at least $n{2}^n$ bit writes, even if the generation state changes only once per object. Useful performance measures therefore distinguish initialization, delay between objects, working memory and the unavoidable output size.

A digital counter following a Gray code, so adjacent output states differ in exactly one bit. The two-bit cycle $00,01,11,10$ is implemented by D flip-flops with next-state functions $G^{+}=H$, $H^{+}=\neg G$.

The order $00,01,11,10$ is a Gray code through the four vertices of $Q_2$. Applying this identification independently in $n$ coordinate pairs makes $[4{]}^n=P_4^n$ a spanning subgraph of the hypercube graph $Q_{2n}$. Therefore every vertex boundary in $Q_{2n}$ contains the corresponding boundary in $[4{]}^n$.

Joe Sawada studies combinatorial generation: efficient ways to list all objects in a specified family. His author homepage highlights Gray codes, where consecutive objects differ by a small change, and De Bruijn sequences, which encode many short words through overlapping windows. These viewpoints make the order of generation part of an algorithm's design.^[ref]

A truth table arranged so neighbouring cells differ in one Boolean variable, using Gray code order along each multi-bit axis. Opposite edges are also adjacent. A valid group contains all $2^k$ combinations of $k$ varying variables while every other variable stays fixed; it eliminates those $k$ variables and gives an implicant; covering the one-cells yields a disjunctive normal form. The method is associated with Maurice Karnaugh.

Write $N[A]$ for the closed graph neighbourhood of $A$. Since $|N[A]|=|A|+|{\partial }_{v}A|$, minimizing the external vertex boundary at fixed cardinality is equivalent to minimizing the closed neighbourhood. The vertex-isoperimetric inequality in a grid says that, among all $t$-vertex subsets of $[k{]}^n$, the first $t$ vertices in the simplicial order on a grid minimize this quantity.

We prove the theorem by mathematical induction on $n$, using the allowed two-dimensional case. Fix a coordinate $i$ and write $A_j\subseteq [k{]}^{n-1}$ for the section in which that coordinate equals $j$. Replace each $A_j$ by the equally large initial simplicial segment $B_j$. By induction, $|N[B_j]|\le |N[A_j]|$. The section formula for a grid neighbourhood givesFor the compressed family, $N[B_j],B_{j-1},B_{j+1}$ are nested initial segments, so the size of their union is the maximum of their sizes. That maximum is no larger than the size of the corresponding uncompressed union. Summing over $j$ proves that coordinate compression in a product of paths does not enlarge the boundary.

Apply these compressions in every coordinate, choosing among boundary-minimizing outcomes one with least coordinate-sum weight. If the result were not an initial simplicial segment, it would contain a later vertex while omitting an earlier one. After cancelling coordinates in which they agree, this gives an inversion in a two-coordinate face. Replacing the occupied portion of that face by the equal-size initial segment in $[k{]}^2$ does not increase its neighbourhood by the assumed two-dimensional theorem, while it strictly lowers the weight. This contradiction is the local-to-global lemma for simplicial grid order, and completes the induction.

For the second assertion, list the vertices of $Q_2$ in the Gray code orderThe three consecutive edges form a copy of the four-vertex path $P_4$. Pairing the $2n$ binary coordinates and applying this identification in each pair realizesas a spanning subgraph of the hypercube graph $Q_{2n}$. For any fixed vertex set, adding graph edges can only enlarge its external vertex boundary. Hence a $t$-set in $Q_{2n}$ has boundary at least that of the same $t$ vertices in $[4{]}^n$, which by hypothesis is at least $s$. Therefore

Arrange each four-variable Karnaugh map in Gray code order $LG=00,01,11,10$ down the rows and $ab=00,01,11,10$ across the columns. For $L^{+}$ the row strings are 0100, 0100, ----, 1110; for $G^{+}$ they are 0001, 1011, ----, 0001. The maps are drawn alongside the state-transition diagram above.

In the $L^{+}$ map, group the whole ab=01 column to obtain $\neg a\wedge b$. Group rows 11,10 with columns 00,01 to obtain $L\wedge \neg a$. Group those same rows with columns 01,11 to obtain $L\wedge b$. The unused-state row permits these larger groups. Symmetrically, in the $G^{+}$ map group column ab=10, rows 01,11 with columns 11,10, and those same rows with columns 10,00 (wrapping around the map). This givesThese expressions drive the D inputs of the two D flip-flops. With $a=b$, both copy their stored bit. With $ab=01$, they force Lt; with $ab=10$, they force Gt. The equations also specify a harmless extension at unused code 11: equal inputs retain it and unequal inputs recover to a valid comparison state. Correct reset is still required. This extension was chosen using don't-cares; the circuit is not claimed to recover from every invalid state without reset.

Let the stored bits be $G,H$, with $G$ most significant. The required Gray code transitions giveConnect $H$ directly to the first D flip-flop's data input and feed $G$ through one NOT gate to the second input. Drive both enable inputs with $E$ and both clock inputs with the same clock. Thus $E=0$ holds both stored bits; $E=1$ takes the next Gray-code counter state at the active clock edge. Reset initializes $GH=00$.

With ordinary uncomplemented $Q$ outputs, one NOT gate is minimal: wiring alone cannot produce $\overline{G}$. If a D flip-flop already provides a complementary output, that output supplies the inversion without an external logic gate. This is a Moore machine because its output $GH$ depends only on stored state; $E$ controls transitions.

Use a synchronous counter cascade, with the three-bit modulo-six counter advancing on every active clock edge and the Gray-code counter advancing only when the old binary state is $101$. Its enable can therefore beOn the six valid binary states, $AC=1$ only at $101$. Both digital counters sample the same clock: at an edge leaving $101$, the binary output becomes $000$ and $GH$ simultaneously advances to the next Gray code. At all other edges $GH$ holds. Starting from $GHABC=00000$, this gives exactly the listed 24-state sequence. Use the shared clock and an enable, rather than making a combinational terminal-state signal into a new clock.^[ref]

For the output $Y$, every state with $C=1$ has $Y=1$. For $C=0$, the only extra high states are $GH=01$ with binary state $010$, and $GH=11$ with binary state $000$ or $100$. On valid states these conditions are $H\overline{G}B$ and $HG\overline{B}$, respectively. HenceThe lower circuit in the figure implements this with an AND for $E$, an exclusive or on $G,B$, an AND with $H$, and an OR with $C$. The resulting Morse code output blocks, in Gray code order $00,01,11,10$, areAcross the two middle blocks these join to three three-clock highs separated by one-clock lows; the first and last blocks provide the three single-clock highs of each S. The specified table is a repeating SOS symbol pattern; its wraparound has a one-clock low, rather than an added inter-message pause. The output is a Moore machine decoding of current stored bits; its value changes after those bits settle.

Use Karnaugh maps with rows $wx$ and columns $yz$, both in Gray code order $00,01,11,10$. Juxtaposition means Boolean conjunction, $+$ means Boolean disjunction, and a bar means Boolean negation. The minimal sum of products forms areandFor $c$, the groups are $\{4,5,6,7\}$, $\{1,3,5,7\}$ and $\{0,1,8,9\}$. For $d$, take $\{8,9\}$, $\{2,3\}$, $\{2,6\}$, $\{0,2\}$ and the isolated minterm $\{5\}$. Every group contains only required ones. The last $c$ group wraps between the top and bottom map rows.

These covers are minimal: $c$ needs its three essential groups, forced by inputs 6, 3 and 8. For $d$, input 5 is isolated, while 9, 3 and 6 each force their respective pair; input 0 still needs a further group. These five groups also attain the minimum literal count of 16.

Use four-variable Karnaugh maps with rows $AB=00,01,11,10$ and columns $Cx=00,01,11,10$, both in Gray code order. A dash denotes an unused present state. The maps for the three next-state bits areFor $A^{+}$, join its sole one with the dash directly below it. For $B^{+}$, use the four-cell groups $Ax$ and $B\bar{C}$, and the two-cell group $\bar{B}Cx$; the last group wraps between the top and bottom rows. For $C^{+}$, join the one at row $01$, column $00$ to the dash below it; the one at row $00$, column $01$ is isolated. These prime implicants giveHere products mean Boolean conjunction and sums mean Boolean disjunction. The $D$ inputs are the desired next-state bits of the three D flip-flops. The equations are independent of the unused values except for the explicitly chosen Karnaugh map groups.

The steady-state output is $q=\bar{a}\bar{c}+bc+\bar{c}d$. Its Karnaugh map, with rows $ab$ and columns $cd$ in Gray code order, isThe existing prime implicants cover adjacent ones except for some transitions in $c$. The consensus theorem supplies the two missing bridging implicants $\bar{a}b$ and $bd$, givingBoth are needed in a hazard-free sum of products retaining the original terms. At $a=0,b=1,d=0$, the two values of $c$ require a common implicant, necessarily covered by $\bar{a}b$; at $a=1,b=1,d=1$, the corresponding transition requires $bd$. Neither bridge covers the other's critical edge. All other adjacent-one pairs already share a term. Thus two is the least number of additional prime implicants. This addresses single-input static hazards; simultaneous input changes require separate analysis.

The minority Boolean function is one at input assignments $000,001,010,100$. Put $a$ on the rows and $bc$ in Gray code order $00,01,11,10$ on the columns. The Karnaugh map has rows $1101$ and $1000$. Pair the cell $000$ with each of its three one-cell neighbours; the horizontal pair across the two map edges is valid because those columns are adjacent.

The pairs giveGenerate $A=\neg a,B=\neg b,C=\neg c$ with three NOT gates. Then useDe Morgan laws show that the final NAND gate computes the required disjunction of the three products. This uses three two-input NAND gates and one three-input NAND gate, besides the input inverters. If only two-input NAND gates are available, replace the final three-input gate by $t=\mathrm{NAND}(n_1,n_2)$, $u=\mathrm{NAND}(t,t)$, $m=\mathrm{NAND}(u,n_3)$.

The three pairs are essential: the one-input assignments $001,010,100$ each have only $000$ as an adjacent one-cell, so no pair can be omitted from this disjunctive normal form.

Write the inputs as $a=2a_1+a_0$ and $b=2b_1+b_0$. Each row compares the represented value of $a$ with all four values of $b$. In Gray code order $00,01,11,10$ along both axes, the Karnaugh map isThe equality cases lie on the diagonal and are all one. A complete row of ones at $a=3$ and a complete column at $b=0$ provide useful checks. The outlined groups are used in the next part.

The Steinhaus-Johnson-Trotter algorithm lists all $n!$ permutations so consecutive entries differ by one adjacent transposition. Start at increasing order with an arrow pointing left on each label. A label is mobile if its arrow points to an adjacent smaller label. Swap the largest mobile label in its arrow direction, then reverse the arrows of every larger label; stop when none is mobile. For three labels this gives 123, 132, 312, 321, 231, 213. Recursively, the largest label sweeps across each smaller-label arrangement in alternating directions, visiting every insertion position once. This gives a Gray code on permutations, useful when an objective can be updated cheaply after a local exchange.