CS Paper Radar

Ranking and Unranking Permutations in Heap's Order

Yusheng Hu

cs.DS ·submitted 2026-10-15 09:00 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Heap-type permutation generation with a prescribed final arrangement

cs.DM math.COcs.DS ·2026-11-17 ·Luís M. S. Russo
theory similarity 0.69
Abstract · 22 pages. Software archived at https://doi.org/10.5281/zenodo.24311260

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.

0.42

FastHeapDict: Permanent Slot Indexing for Efficient Decrease-Key Operations in Indexed Priority Queues

cs.DS ·2026-10-30 ·Hojjat T. Goudarzi, Arash Torabi Goodarzi, Mohammad Amir Eshraghi
code/data similarity 0.55
Abstract · 9 pages, 8 figures. Preprint; Python and C++20 implementations. Source code and benchmark artifacts available at https://github.com/hojjatgo…

Efficient decrease-key support remains an important practical concern in priority queues used by shortest-path and graph-processing algorithms. Although duplicate-entry heaps avoid explicit decrease-key operations and are simple to implement, they may accumulate many stale entries when tentative priorities are repeatedly improved. This paper presents FastHeapDict, an indexed binary min-heap based on permanent slot indexing. Instead of repeatedly locating keys through hash-table lookups during heap repair, FastHeapDict assigns each key a stable integer slot and stores that slot directly in heap entries. As a result, position updates during sift-up and sift-down operations are performed through integer indexing while preserving the usual indexed-heap interface. We evaluate FastHeapDict in both Python and C++20 using Dijkstra's algorithm as the primary experimental workload. The benchmarks include constructed dense stress graphs, randomized dense graph variants, and comparisons against duplicate-entry heaps and existing priority-queue alternatives. Across the tested Python workloads, FastHeapDict consistently outperforms the duplicate-entry heapq baseline and the tested heapdict and pqdict implementations. In the C++20 implementation, FastHeapDict also achieves strong constant-factor improvements over std::priority_queue duplicates, std::set-based decrease-key, and std::multiset duplicates. These results indicate that permanent slot indexing can provide a compact and effective implementation strategy for indexed priority queues in workloads where priority updates are frequent.

0.40

Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time

cs.DS ·2026-10-07 ·Lei Dong, Dennis Wong, Bowie Liu, Rui Bao, Lin Chen +2 more
similarity 0.55
Abstract · 38 pages, 4 figures

A graph $G$ is $k$-degenerate if there exists an ordering $v_1, v_2, \dots, v_n$ of its vertices such that each vertex $v_i$ has at most $k$ neighbors $v_j$ in $G$ with $j < i$. A well-ordered $k$-degenerate graph is a labeled graph on the vertex set $\{1, 2, \dots, n\}$ in which every vertex $i$ has at most $k$ neighbors among $1, 2, \dots, i-1$. We present the first simple algorithms that generate, rank, and unrank cyclic pivot Gray codes for well-ordered $k$-degenerate graphs, where consecutive graphs differ by the addition, removal, or pivoting of a single edge. Our algorithm generates each well-ordered $k$-degenerate graph in constant amortized time per graph, using $O(n^2)$ space, while ranking and unranking take $O(n^2)$ time and $O(n^2)$ space.

0.30

Unranking $S$-avoiding permutations with two forbidden offsets

cs.DM math.CO ·2026-10-09 ·Antônio Augusto André
similarity 0.55
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

Straightforward Entropy-Sensitive Mergesort

cs.DS ·2026-08-11 ·Bill Jin, Alex Zihan Xu
similarity 0.53
Abstract · 21 pages, 15 pages main text, 4 pages appendix, 2 figures

In this paper, we present a stable mergesort variant, "directional mergesort", that to sort an array of $n$ elements makes no more than $nH+3n$ comparisons and $1.5nH+O(n)$ moves where $H$ is the run-based entropy of the input sequence, matching the best existing algorithms in run-adaptive sorting. However, our algorithm is surprisingly minimalistic: it leverages only skip checks, i.e., bypassing the merge step when both halves are already in order, and dynamically changing the direction of merging based on the state of the subarrays. As dynamic run scanning is avoided, all merge steps remain static and derivable from $n$, enabling a reduction to $O(1)$ words of stack space (i.e. space usage excluding the merge buffer) in "directional mergesort$^{++}$", thus improving over the predecessors' $O(\lg n)$ words. Importantly, as directional mergesort adapts only to non-decreasing runs, directional mergesort$^{++}$ also applies a parallel set of rules for (strictly) decreasing runs, allowing the algorithm to also adapt to decreasing runs whilst retaining the original comparison bounds.

0.10

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.53
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

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

cs.DM math.CO ·2026-10-03 ·Satyam Tyagi
theory similarity 0.53
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

Incremental Open Addressing Has No Time-Space Tradeoff

cs.DS ·2026-11-03 ·Martín Farach-Colton, Andrew Krapivin, William Kuszmaul
similarity 0.52
Abstract · 46 pages, 4 figures, 1 table

In this paper, we show that there is no time-space tradeoff in incremental open addressing: there is an incremental open-addressed hash table that supports $O(1)$ worst-case expected time insertions, positive queries, and negative queries, at any load factor (even load factor $1$). As an intermediate result, we also revisit the problem of constructing an incremental open-addressed hash table that does not perform reordering (does not move elements around over time). In this setting, we show that it is possible to get $O(1)$ amortized expected positive query time together with $O(1)$ worst-case expected insertion time, a combination that was not previously known to be possible.

0.19