CS Paper Radar

Heap-type permutation generation with a prescribed final arrangement

Luís M. S. Russo

cs.DM math.COcs.DS ·submitted 2026-11-17 13:44 UTC · v1
theory

Abstract

Heap's algorithm generates all permutations of an array of n items, obtaining each one from its predecessor by a single swap. We determine the net permutation applied to the array by every complete recursive call: a transposition when the number of items is odd and at least three, and a cycle through all items when it is even. We show that the output of each call is a concatenation of right cosets of the symmetric group on one item fewer, and we prove a general formula: the order in which the items are parked at the last position may be chosen freely, every such order corresponds to exactly one valid schedule, and it determines the net permutation of the call. Two variants follow. In the cyclic variant a complete sweep over an even number of items rotates the array by one position. In the extremal variant, for even n, a sweep started from the identity ends in the lexicographically largest arrangement that any single-swap enumeration can leave; by a parity argument this is the reversal exactly when n is congruent to 2 modulo 4. The construction of the extremal variant is proved correct when n is divisible by 4 and verified by computer for all even n up to 10000.

Comment
22 pages. Software archived at https://doi.org/10.5281/zenodo.24311260

Closest papers

Nearest neighbours by meaning across the whole index.

Ranking and Unranking Permutations in Heap's Order

cs.DS ·2026-10-15 ·Yusheng Hu
similarity 0.69
Abstract

Heap's algorithm is a permutation generation method with very low constant overhead. Its element-interchanging mechanism, however, prevents the standard factorial-base Lehmer code from being applied directly, and to our knowledge no explicit Rank/Unrank algorithm for the Heap order has been published. This paper describes the block structure of Heap's algorithm in terms of rearrangement operators: the net effect of a block-internal traversal is a tail-preserving operator and the block-boundary swap is a top-level swap operator, and together they yield a closed-form recurrence for the block transitions. On this basis a bottom-up Unrank algorithm and a top-down Rank algorithm are built from one and the same closed-form in-block mapping; both run in $O(n^3)$ time and $O(n)$ space and require no factorial-scale precomputed table. The supporting proofs use a synchronized strong induction on the dimension to establish the bijectivity of the trailing-element mapping, closed forms for the final arrangement and for the trailing sequence, the dichotomy of its cycle structure, and the reciprocity of Rank and Unrank. The Heap order is in fact the colex order of the mixed-radix code.

0.26

Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231

cs.DM math.COcs.DScs.LO ·2026-09-14 ·Henning Arnór Skeggi Úlfarsson
code/data similarity 0.69
Abstract · 36 pages, 4 figures, 1 table. v2: revised and shortened exposition, corrected account of prior work, the first 151 terms tabulated, a proved…

We give an algorithm counting the permutations that avoid a fixed pattern of the following form: the direct sum of an increasing pattern and 231. The first members of the family are 1342 and 12453. For each member the algorithm uses polynomially many operations and stored integers, with degrees that grow linearly in the length of the pattern. It comes from a recurrence that reads a permutation from left to right and records the constraints that the letters read so far impose on those still unread. This recurrence has exponentially many states, but part of each state is protected: later steps carry it along unchanged and do not depend on it, and factoring the protected part out leaves a dynamic program of polynomial size. For 12453 a translation symmetry sharpens the bounds to degree seven for the operations and degree four for the storage. We also compute the number of 12453-avoiding permutations of every length up to 150. The previously published series, due to Biers-Ariel (2019), reached length 38. We also give a sampler of uniformly random avoiders. A floating-point implementation of it, proved to be within total variation distance $3.5\cdot10^{-5}$ of uniform for ideal random bits, draws the one million 12453-avoiding permutations of length 300 shown in a heatmap. The literal and kernel recurrences for 1342 and 12453 are verified in the Lean 4 proof assistant.

0.32

Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori

cs.DM math.CO ·2026-09-23 ·Tim Gerlach, Elizabeth Hartung, Pia Herkenrath, Joe Sawada, Aaron Williams
similarity 0.68
Abstract

A de Bruijn sequence packs all $n$-bit binary words into a cycle of length $2^n$. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when $n = 2m + 1$ is odd and the torus and windows have two rows (i.e., the torus is a "tworus"). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into $2^{m-1}$ matching blocks where each block contains the same sequence of unordered columns. Furthermore, given one such block we can generate each successive column of a tworus in amortized $\mathcal{O}(1)$-time. We also prove non-existence results for certain sizes of tori and provide algorithms for constructing multiversal cycles (perfect necklaces) of unlabeled binary words.

0.23

Unranking $S$-avoiding permutations with two forbidden offsets

cs.DM math.CO ·2026-10-09 ·Antônio Augusto André
similarity 0.68
Abstract · 6 pages

Given a finite family of combinatorial objects with a total order, ranking asks for the position of a given object, and unranking asks for the object occupying a given position. Both provide algorithmic access to families too large to enumerate. Kagey gave a polynomial-time algorithm for several position-restricted families and left open the case of $\{-1,1\}$-avoiding permutations. We show that when $|S| = 2$, the graph of forbidden squares is $2$-regular, a disjoint union of cycles, and that fixing a prefix leaves only paths and untouched cycles. This yields polynomial-time prefix counting, ranking and unranking for every two-element set of offsets, covering $\{-1,1\}$. The same structure gives a short proof that the number of $\{-1,1\}$-avoiding permutations equals the $n$-th ménage number for odd $n$ and exceeds it by $2$ for even $n$, proving a conjecture recorded in the OEIS entry A354152.

0.20

Parity and Pattern Detection in Permutation Streams

cs.DS ·2026-09-08 ·Mark Braverman, Or Zamir
similarity 0.61
Abstract

Consider a permutation of $[n]$ whose values arrive one at a time. We resolve two questions about the space needed to decide natural properties of such input: First, computing the parity of the permutation requires $Θ(n)$ bits, even with randomization and constant error, and a constant number of passes. Second, every permutation pattern of length three can be detected deterministically in one pass using $O(\log n)$ bits. Together with the 2026 lower bounds of Berendsohn, this completes the classification of fixed permutation patterns; The optimal space complexity is $Θ(\log n)$ for monotone patterns and patterns of length at most three, and $Θ(n)$ for every other pattern. As a consequence, we observe that we can verify BST traversals in streaming with logarithmic memory.

0.43

Enumeration Complexity of Permutation Classes

cs.CC math.CO ·2026-10-27 ·Manuel Bodirsky, Mohamed Elsheikh
theory similarity 0.60
Abstract

We study classes of permutations that are defined by avoidance of forbidden patterns. For each fixed finite set $B$ of forbidden patterns, we study the \emph{avoider enumeration problem}: given an integer $n$, output all $B$-avoiding permutations of length $n$. Avoider enumeration is output-polynomial for every fixed $B$. However, our main notion of efficiency is polynomial delay. We use the insert-maximum tree as a search tree, in which permutations are built by repeatedly inserting a new maximum while preserving pattern avoidance. This leads to the \emph{insert-maximum extension problem}, which asks if a given permutation has an avoiding descendant at a specified depth. An algorithm for this problem can prune branches that cannot reach the target length. Hence, if this problem is in P, we obtain polynomial-delay enumeration. To investigate this problem, we introduce and study \emph{pockets}, the maximal finite subtrees of the insert-maximum tree. For fixed $B$, if there is a polynomial $p$ such that every pocket rooted at $ρ$ has at most $p(|ρ|)$ nodes, then the extension problem is solvable in polynomial time and enumeration has polynomial delay. In particular, a bound on pocket depth depending only on $B$ suffices. We prove such a bound if the class is well-quasi-ordered, has a regular insertion encoding, or if $B$ omits one of the three maximum-position types: leftmost, interior, or rightmost. We also prove that extension is in NP for every fixed $B$, even with binary-encoded target depth. On the negative side, we construct a fixed set of $55$ forbidden patterns for which extension is NP-complete. Consequently, enumerating valid extensions from a given starting permutation cannot have polynomial delay unless P=NP. This also answers a question of Hanika by showing that the forbidden permutation constraint satisfaction problem can be NP-complete for a fixed forbidden set.

0.08

A proof of Lehmer's permutation conjecture for neighbor-swap graphs

cs.DM math.COcs.LO ·2026-10-01 ·Tom Verhoeff
theory similarity 0.59
Abstract · 29 pages, 3 figures

In 1965, D. H. Lehmer conjectured that the permutations of every multiset admit an imperfect Hamiltonian traversal by adjacent swaps: a walk in the neighbor-swap graph that visits every word, with some words visited twice in order to reach a neighbor and return. The question is posed as an unsolved research problem in Knuth's Art of Computer Programming. Verhoeff (2017) chose the stutter words, in which every domino is a double, as the words to be reached this way, and reformulated the conjecture as the Hamiltonicity of the graph $N(S)$ on the non-stutter words, with two exceptional families --- binary signatures with an odd multiplicity, and the permutations of $(2k,1,1)$ --- that admit a Hamiltonian path but no cycle. This article proves the reformulated conjecture, and with it Lehmer's conjecture. The key structure is a partition of the words into hypercubes: the swaps inside dominoes turn each class of words with the same domino contents into a hypercube, and the stutters are exactly the $0$-dimensional classes. When every multiplicity is even, Hamiltonian cycles of the hypercubes are glued along a spanning tree, with no finite check. The case of exactly one odd multiplicity reduces to the all-even case and to a theorem of Stachowiak (1992), the one inherited Hamiltonicity input, which also settles two or more odd multiplicities. The only finite ingredients are two explicit cycles, of 28 and 84 words. Every construction is implemented in Python and checked against brute-force graphs, and the proof is formalized in Lean 4 over Mathlib.

0.31

Removing $m$ from $m$-pile Divisor Nim

cs.DM math.CO ·2026-10-03 ·Satyam Tyagi
theory similarity 0.57
Abstract · 23 pages, 15 tables

In Divisor Nim, a player removes from one heap a positive number of stones that divides the size of every other heap. We prove that the Sprague--Grundy (SG) value satisfies $g(P)\le 2h_{\min}+\lfloor\log_2h_{\min}\rfloor$, where $h_{\min}$ is the smallest nonempty heap, independently of the number and sizes of the other heaps. The proof starts with odd heaps and classifies removals by their factors of $2$. The largest heap in a starting board then supplies an SG bound valid throughout every successor chain. When one heap varies, we sharpen Morisawa's eventual-period bound: the smallest fixed heap controls the SG value range, the number of consecutive values compared, and an increase in the varying heap that repeats legal moves. The remaining dependence on the fixed board lies in the SG periods of direct successors. Using the largest fixed heap, we derive an explicit common period for all these recursive layers. Its possible prime divisors belong to a fixed finite set, independent of heap count; their exponents remain controlled by the total fixed stones. Finally, joining boards under one shared divisor rule preserves and can tighten the SG ceiling. Minimum 2-adic depth and its count parity determine every joined outcome, and a join with at least two odd heaps has exact SG value $0$ or $1$. We close with two conjectures: $g(P)\le2h_{\min}$, and that the least eventual SG period, when one heap varies, divides $2\operatorname{lcm}(1,\ldots,h_{\max})$. Here $h_{\max}$ is the largest fixed heap, excluding the varying heap. The second claim would remove heap-count dependence from the period bound as well.

0.30