Every ordering once, around a cycle

A cycle of eight bits shows every three-bit word exactly once as a window of three consecutive bits. The same trick works for words of any length over any alphabet, because the windows overlap in a way that makes a graph with equal numbers of arrows in and out at every vertex, and such a graph always has a closed walk using every arrow once. For pairs of things it works sometimes and fails sometimes, and the failure is decided by the parity of a degree.

For orderings it fails completely, and the failure is instructive. There are six orderings of the three symbols 1, 2, 3 — the permutations 123, 132, 213, 231, 312 and 321 — so the natural hope is a cycle of six symbols in which each window of three consecutive symbols is a different one of them. No such cycle exists, and none exists for four symbols either, or for any number beyond two. This essay draws the reason, and then two ways around it that do work: one that restores the graph and lets Euler’s theorem do everything, and one that works without any graph at all.

The window that forces a repeat #

Suppose a window of three consecutive symbols is a permutation of 1, 2, 3, so it holds each symbol exactly once. The next window drops the first symbol of this one and keeps the other two. For it also to hold each symbol once, the symbol it adds must be the only one missing from those two, which is exactly the symbol that was just dropped.

So every symbol equals the one three places before it, and the sequence is periodic with period three. It shows three windows — 123, 231, 312 — and then repeats them. The other three orderings, the reversed ones, can never appear in the same sequence. The same argument works for any number $n$ of symbols: a window holding all $n$ forces period $n$, and a cycle of period $n$ shows $n$ of the $n!$ permutations.

Nothing in the count warns of this. There are $n!$ permutations and a cycle of length $n!$ has exactly $n!$ windows, so the counting condition that decides the easy cases is satisfied perfectly. The obstruction is the overlap itself: two consecutive windows share $n - 1$ symbols, and $n - 1$ distinct symbols out of $n$ leave no freedom at all for the next one. The search in the figure checks this directly rather than relying on the argument: every cycle of six symbols over three, and every cycle of twenty-four over four, was generated and tested.

Writing each ordering by all but its last entry #

The first repair changes what a window has to show. A permutation of $n$ symbols is determined by its first $n - 1$ entries, since the last is whichever symbol has not yet appeared. So write each permutation in shorthand — 12 for 123, 13 for 132, and so on — and ask for a cycle over $n$ symbols in which each window of $n - 1$ is the shorthand of a different permutation.

That removes the obstruction. Two consecutive windows now overlap in $n - 2$ symbols, which leave two symbols unused, so there are two ways to continue from any window, not one. And the overlap structure turns out to be exactly the kind that Euler’s theorem handles.

Make a graph whose vertices are the arrangements of $n - 2$ symbols and whose arrows are the arrangements of $n - 1$ symbols: an arrangement $a_1 a_2 \ldots a_{n-1}$ runs from the vertex $a_1 \ldots a_{n-2}$ to the vertex $a_2 \ldots a_{n-1}$. The arrows are exactly the shorthand permutations, $n!$ of them. For three symbols the vertices are single symbols and the arrows are ordered pairs: a triangle with arrows both ways along every side.

At every vertex two arrows leave, one for each of the two symbols the vertex does not contain, and two arrive, one for each symbol that could have been dropped from the front. So the graph is balanced, like the de Bruijn graph for words, and connected, and Euler’s theorem — the one the bridges of Königsberg started — says it has a closed walk using every arrow exactly once. Reading off the last symbol of each arrow along the walk gives a cycle of $n!$ symbols whose windows of $n - 1$ are all the arrows, each once.

The ring for three symbols is short enough to check by eye. Reading clockwise from the top, the windows are 21, 13, 32, 23, 31, 12, and completing each with its missing symbol gives six different permutations. The six-symbol cycle over three symbols is the thing the naive version could not produce, and the only price is that the last entry of each permutation is left implicit.

Four symbols, twenty-four orderings #

For four symbols the graph is larger and the argument is the same. The vertices are the twelve ordered pairs of distinct symbols, and the arrows are the twenty-four ordered triples: $abc$ runs from $ab$ to $bc$.

The picture is tangled, and it does not matter. The only facts Euler’s theorem needs are local — two in and two out at each vertex — and the fact that the graph is connected, which the circuit itself demonstrates by visiting everything. Hierholzer’s method, which walks until it is stuck and then splices in detours from vertices with unused arrows, finds a circuit in time proportional to the number of arrows.

The same construction works for every $n$, and the balanced degree is always two, because a vertex is missing exactly two symbols. That is the whole existence proof, and it is due to Brad Jackson in 1993. Frank Ruskey and Aaron Williams later gave an explicit rule that generates such a cycle one symbol at a time without building the graph, in the spirit of writing necklaces in order rather than searching for an Euler circuit.

Keeping every entry, with one symbol more #

The second repair keeps whole windows of $n$ symbols but relaxes what a window must be. Allow $n + 1$ symbols, and ask only that each window of $n$ be order-isomorphic to a different permutation: its entries arranged in the same relative order. The window 2, 4, 1 counts as the pattern 231, because its middle entry is largest and its last is smallest. It is the same notion of relative order that decides whether a sequence climbs or falls: only the comparisons between entries matter, never their values. Fan Chung, Persi Diaconis and Ron Graham proposed this in 1992 as the natural version for permutations.

The extra symbol is what breaks the forced repeat. A window of three distinct symbols out of four leaves one symbol unused, so the next symbol has two candidates that keep the window’s entries distinct: the one just dropped, or the one that was never there. And order-isomorphism is coarser than equality, so many different windows count as the same pattern, which gives the search room.

What the extra symbol does not give is a balanced graph. The patterns of consecutive windows are related by an overlap of $n - 1$ entries, but whether the next window has a given pattern depends on the actual values, not only on the previous pattern, so there is no graph on patterns in which every cycle is a walk. The existence question has to be settled another way.

For four symbols the search finds such cycles on five symbols, and none on four. Chung, Diaconis and Graham conjectured that $n + 1$ symbols always suffice, and that it cannot be done with $n$; the second half is the forced-period argument above. J. Robert Johnson proved the first half in 2009, with a construction that works for every $n$ — an argument that builds the cycle directly, since no Euler graph was available to do it.

How many there are #

The two repairs differ in something beyond their proofs, and a count makes the difference visible.

For shorthand cycles there is a formula. The number of Euler circuits in a balanced graph is given by the BEST theorem — after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte — as the number of spanning trees directed into any one vertex, times a product of factorials of out-degrees less one. Here every out-degree is two, the factorials are all one, and the count is a single determinant that counts trees. It gives three cycles for three symbols and 384 for four, and the figure checks both against an exhaustive search, which finds each cycle once from each of its starting points. For five symbols the determinant gives 7,044,820,107,264,000 cycles, far beyond any search.

For order-isomorphic cycles there is no such formula. The search finds four cycles for three symbols and 84 for four, and there the counting stops. Nothing like the tree count is available, because the structure that would make the cycles walks in a graph is exactly what is missing. The two repairs solve the same problem, and one of them is a theorem about graphs while the other is a construction with no graph behind it.

A window as an address #

A universal cycle is an addressing scheme, which is where most of its uses come from. In a de Bruijn cycle of bits, any window names its own position, since it occurs exactly once; that is how a page can know where it is from a few marks, and how a register of four bits can step through every state without repeating one. A shorthand cycle for permutations does the same for orderings: any $n - 1$ consecutive symbols of it identify one position, and at that position a whole ordering of $n$ things.

The idea has a well-known performing form. Persi Diaconis and Ron Graham, two of the three authors who posed the permutation problem, describe card tricks built on de Bruijn cycles: a deck is arranged so that the colours of any five consecutive cards, cut anywhere, identify the cards exactly, and the performer names five cards from five spoken colours. The arrangement works because the colour sequence is a cycle in which every window of five is different. The same arrangement could be made to reveal an ordering rather than a colour pattern, and the shorthand cycle is what it would have to use, since the naive version does not exist.

The shorthand cycle is also a way of listing permutations with the least possible change between neighbours. Consecutive windows share $n - 2$ symbols, so each permutation in the list differs from the next by moving one symbol from the front to a new position near the back. Listings of that kind — every object once, each step a small change — are called Gray codes, and the shorthand cycle is one in which the step is always the same kind of move. Ruskey and Williams’s rule generates it in constant time per symbol, which matters when $n!$ is large and the cycle is being read as it is produced rather than stored.

None of those uses survives the relaxation to order-isomorphic windows unchanged. An order-isomorphic window names a pattern, not a position, and many positions of a cycle over $n + 1$ symbols can show windows with the same values in different places. What the order-isomorphic cycle offers instead is economy: one extra symbol, rather than implicit entries, and every pattern visible in full.

Why the shorthand graph is balanced #

It is worth seeing that the balance of the shorthand graph is not a lucky accident, because the same reasoning explains why the naive version has no graph at all.

In any cycle whose windows are some family of objects, a window determines the overlap it shares with the next, and the question is how many continuations each overlap allows and how many windows can lead into it. For words over $k$ letters, an overlap of $n - 1$ letters allows $k$ continuations and receives from $k$ predecessors: balanced. For shorthand permutations of $n$ symbols, an overlap of $n - 2$ distinct symbols allows two continuations and receives from two: balanced. For full permutations of $n$ symbols, an overlap of $n - 1$ distinct symbols allows one continuation and receives from one: balanced, but trivially, and the resulting graph is a disjoint union of short cycles, each of length $n$. Balance is necessary for an Euler circuit but connectedness is too, and the naive graph fails the second condition, not the first.

That reading turns the forced-period argument into a statement about a graph falling apart. Every permutation window leads to exactly one other, so the windows fall into cycles of length $n$ — the rotations of each permutation — and no single walk can visit more than one of them. There are $(n-1)!$ such cycles, and a universal cycle would need them to be one.

What the search cannot show #

Every existence claim drawn here for a particular size is checked: the cycles are generated, and every window is tested. The claims for every size come from arguments — the Euler argument for shorthand cycles, Johnson’s construction for order-isomorphic ones, and the forced period for the impossibility — and the searches confirm them only at three and four symbols.

The counts are exact where they are stated. The BEST count for five symbols is a determinant of a 59-by-59 matrix computed in exact integer arithmetic, not a search. The order-isomorphic counts for five symbols and beyond are not computed here; the search space at five symbols is large enough that exhausting it is a real computation, and the numbers are not ones this essay can vouch for.

And order-isomorphism is one relaxation among several. Asking for windows whose entries are distinct but otherwise arbitrary, or for windows that are permutations up to cyclic rotation, gives different problems with different answers. The two versions here are the ones whose answers are complete theorems.

Still open: the shortest string holding every ordering #

A different question drops the cycle and asks for the shortest string, not wrapping round, that contains every permutation of $n$ symbols as a block of $n$ consecutive symbols — a superpermutation. Here the windows are full permutations, the overlap trick is not available, and neighbouring permutations have to share as much as they can.

For $n$ up to five the shortest lengths are known: 9, 33 and 153 for three, four and five symbols, which are $1! + 2! + \cdots + n!$. That formula was conjectured to hold in general, and it fails: in 2014 Robin Houston found a superpermutation on six symbols of length 872, one shorter than the formula’s 873. The shortest length for six symbols is still not known, and neither is the growth of the shortest length in general, although the best upper and lower bounds are now close.

The contrast with the cycles above is complete. When the windows can be arranged as the arrows of a balanced graph, existence is a single theorem and the count is a determinant. When they cannot, even the shortest string containing them all is an open problem at six symbols.

What the shorthand buys #

The three versions of the question differ by what a window has to be. A window that must be a whole permutation leaves no freedom for the next symbol, and the cycle collapses into short loops. A window that is a permutation with its last entry left implicit leaves exactly two choices everywhere, and Euler’s theorem does the rest. A window that is only a pattern leaves enough freedom for cycles to exist, but not in a form any graph records.

That is the general lesson of universal cycles, and permutations show it most sharply. Existence is easy exactly when the overlaps of consecutive windows form a balanced, connected graph. Changing the encoding of the objects can create that graph where there was none, and the shorthand for permutations is the cleanest example: dropping one redundant symbol from every window turns an impossibility into an Euler circuit.