Wiggly permutations were introduced by Bapat and Pilaud (Wigglyhedron Mathematische Zeitschrift 2025). We positively answer one of their conjectures by finding a Hamilton path in the wiggly flip graph that is isomorphic to the wigglyhedron. Our path provides a Gray code in which successive wiggly permutations are obtained by a single jump or hop, meaning that one or two consecutive symbols move past some number of smaller symbols. The Gray code has a simple greedy description that produces a recursive zig-zag pattern reminiscent of plain changes for permutations. More broadly, our results extend Algorithm J and the series of papers on zig-zag languages initiated by Hartung, Hoang, Mütze and Williams (Combinatorial Generation via Permutation Languages SODA 2020). Finally, we use wiggly changes as the basis for an 𝒪(n)-time delay generation algorithm.

Early video games didn’t have hardware support for random number generation, so developers used software-based RNG. We show that hundreds of games in the Nintendo Famicom / NES library regenerate the same pseudorandom sequence of 32, 767 bits, although the machine code for doing so comes in more than one hundred variants. We identified the disparate implementations using a simple regular expression that matches the following “fingerprint” of operations: LDA, AND, STA, LDA, AND, EOR, CLC, BEQ, SEC, ROR. These instructions implement a classic 15-bit linear feedback shift register associated with x15 + x7 + 1 (i.e., tap the 15th and 7th bits). However, many games devoted more memory to the LFSR’s state. For example, Donkey Kong (1983) used 8 bytes (or 8 · 8 = 64 bits), The Legend of Zelda (1986) used 13 bytes, and Super Mario Bros. 3 (1988) used 9 bytes. In each case, additional entropy is lost by a simple programming error: the bits are shifted in the wrong direction.

In this work we present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations. This approach provides a unified view on many known results and allows us to prove many new ones. In particular, we obtain the following four classical Gray codes as special cases: the Steinhaus-Johnson-Trotter algorithm to generate all permutations of an n-element set by adjacent transpositions; the binary reflected Gray code to generate all n-bit strings by flipping a single bit in each step; the Gray code for generating all n-vertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an n-element ground set by element exchanges due to Kaye. We present two distinct applications for our new framework: The first main application is the generation of patternavoiding permutations, yielding new Gray codes for different families of permutations that are characterized by the avoidance of certain classical patterns, (bi)vincular patterns, barred patterns, Bruhat-restricted patterns, mesh patterns, monotone and geometric grid classes, and many others. We thus also obtain new Gray code algorithms for the combinatorial objects that are in bijection to these permutations, in particular for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into n rectangles subject to certain restrictions. The second main application of our framework are lattice congruences of the weak order on the symmetric group Sn. Recently, Pilaud and Santos realized all those lattice congruences as (n – 1)-dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc. Our algorithm generates the equivalence classes of each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian. We thus also obtain a provable notion of optimality for the Gray codes obtained from our framework: They translate into walks along the edges of a polytope.

Knuth assigned the following open problem a difficulty rating of 48/50 in The Art of Computer Programming Volume 4A : For odd n ≥ 3, can the permutations of { 1,2,… , n } be ordered in a cyclic list so that each permutation is transformed into the next by applying either the operation σ, a rotation to the left, or τ, a transposition of the first two symbols? The Sigma-Tau problem is equivalent to finding a Hamilton cycle in the directed Cayley graph generated by σ = (1 2 ⋅ n ) and τ = (1 2). In this article, we solve the Sigma-Tau problem by providing a simple O ( n )-time successor rule to generate successive permutations of a Hamilton cycle in the aforementioned Cayley graph.

We present a simple framework for constructing$k$-ary de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes several previously known de Bruijn sequence constructions based on the pure cycling register and is applied to derive a new construction that is perhaps the simplest of all successors. Furthermore, it generalizes an algorithm to construct binary de Bruijn sequences based on any arbitrary nonsingular feedback function. The framework is applied to derive and prove the correctness of successors to efficiently construct 1) universal cycles for$k$-ary strings of length$n$whose weight is bounded by some$w$and 2) universal cycles for permutations. It has also been subsequently applied to find the first universal cycle constructions for weak orders.

Nijenhuis and Wilf asked the following question in their Combinatorial Algorithms textbook from 1975: Can the permutations of {1, 2, …, n} be ordered so that each permutation is transformed into the next by applying either the operation σ, a rotation to the left, or τ, a transposition of the first two symbols? Knuth rated the challenge of finding a cyclic solution for odd n (cycles do not exist for even n > 2) at 48/50 in The Art of Computer Programming, which makes it Volume 4's hardest open problem since the ‘middle levels’ problem was solved by Mütze. In this paper we solve the 40 year-old question by Nijenhuis and Wilf, by providing a simple successor rule to generate each successive permutation. We also present insights into how our solution can be modified to find a Hamilton cycle for odd n.

De Bruijn sequences are circular strings of length $2^n$ whose length n substrings are the binary strings of length n. Our focus is on creating circular strings of length $\binom{n}{w}$ for the binary strings of length n with weight (number of 1s) equal to w. In this case, each fixed-weight string can be encoded by its first $n{-}1$ bits since the final bit is redundant. For this reason, we construct circular strings of length $\binom{n-1}{w}+\binom{n-1}{w-1}$ whose length $n{-}1$ substrings are the binary strings of length $n{-}1$ with weight w or $w{-}1$. Our construction is reminiscent of the construction for the lexicographically least de Bruijn sequence, except the underlying algorithm is applied to cool-lex order instead of lexicographic order. The construction can be efficiently implemented so that successive blocks of n bits are generated in constant amortized time while using $O(n \log n)$-space. This article's results were also used to create de Bruijn sequences for binary strings of length n with a specified maximum weight.

We show how to construct an explicit Hamilton cycle in the directed Cayley graph C → ({σ n , σ n -1 }: S n ), where σ k is the rotation (1 2 … k ). The existence of such cycles was shown by Jackson [1996] but the proof only shows that a certain directed graph is Eulerian, and Knuth [2005] asks for an explicit construction. We show that a simple recursion describes our Hamilton cycle and that the cycle can be generated by an iterative algorithm that uses O ( n ) space. Moreover, the algorithm produces each successive edge of the cycle in constant time; such algorithms are said to be loopless . Finally, our Hamilton cycle can be used to construct an explicit universal cycle for the ( n -1)-permutations of a n -set, or as the basis of an efficient algorithm for generating every n -permutation of an n -set within a circular array or linked list.

This paper answers the following mathematical question: Can multiset permutations be ordered so that each permutation is a prefix shift of the previous permutation? Previously, the answer was known for the permutations of any set, and the permutations of any multiset whose corresponding set contains only two elements. This paper also answers the following algorithmic question: Can multiset permutations be generated by a loopless algorithm that uses sublinear additional storage? Previously, the best loopless algorithm used a linear amount of additional storage. The answers to these questions are both yes.