Heap's algorithm: Ranking and unranking functions

@cfcs, July 2026

TL;DR

• unrank(n:nat, rank: nat) -> Permutation:array:

  "Seek"/skip to a numbered permutation output by Heap's algorithm for an array of length n.

• rank(Permutation:array) -> rank:nat:

  Identify the offset ("rank") of a given permutation from the start.

Introduction

Heap's algorithm generates all permutations of an array of length n by swapping exactly two elements at each "step". Its simplicity of implementation and low overhead per step sometimes makes it an attractive alternative to lexicographical enumeration of permutations which requires division calculations that can be costly.

One would think that these properties would also make Heap's algorithm popular for parallel / distributed computations on permutations, but in order to split up the work of processing the $n$ permutations, a method to "resume" Heap's algorithm from a distant offset/rank is required. Unfortunately the Internet isn't exactly abundant with implementations of such unranking functions; I couldn't find any.

How it works

Besides touching only two elements per step, Heap's algorithm has other interesting properties:

1. The algorithm works by transposing two elements per step (swapping by indices), and never examines the element values. This means the resulting pattern is the same for any n (and solely dependent on n).

2. The prefix permutation repeats, for example the permutations of n will consist of the permutation pattern for $n-1$ applied n times, with an additional swap at the end. We can use this property to "fast-forward" by caching these end-state prefix permutations and keeping track of how many times they would have been applied.

This yields an $O(n^3)$ solution, which is "slow", but it's a lot faster than $O(\text{factorial}(n))$, and thus enables parallel programs to use Heap's algorithm for enumerating the permutations. Pay for the expensive unrank call t times, one for each of your threads, and use the original algorithm from there to step through the permutations in parallel chunks of $n! / t$.

3. It is perhaps also worth mentioning that fewer than $n-1$ prefixes are needed for small $k$; for example $k = 0$ does not make use of the prefix-enabled skipping.

4. Update Aug 2026: unrank_noprecomp() runs in $O(\frac{1}{2}n^2)$ time without the precomputations by unrolling the transformations performed by the precomputation tables.

5. See tests/kat.rs:precompute_kats() for an alternative solution that trades the need for prefix tables for more processing per unrank/rank.

Source code index

So here are a couple of implementations, based on exploiting the property that the prefix permutations repeat. Note that since the rust code uses usize, overflows for n > 20 aren't handled. The python implementation is backed by a bigint library and should work correctly for any n and k.

Rust source code in src/lib.rs:

• pub fn unrank(prefixes, n, k): return the k'th output of Heap's algorithm in $O(\frac{1}{2}n^3)$ time.

  • python: heaps.py:HeapUnranker.unrank_loop(self, n, k)

• pub fn unrank_noprecomp(n,k): like unrank(n,k), but using fn precomp_digit(n,i) instead of the precomputation table. See tests/kat.rs:precompute_kats for examples. This runs in $O(\frac{1}{2}n^2)$ time with $O(3n)$ memory.

• pub fn unrank_recursive(n,k): functional, immutable, slow version of unrank()

  • python: heaps.py:HeapUnranker.unrank(self, n,k) (more or less)

• pub fn precompute(n): Precompute the prefix permutations up to n in $O(\frac{1}{2}n^3 + n)$ time and $O(\frac{1}{2} n^2)$ space. Needed for unrank(prefixes, n, k) and rank(prefixes, permutation).

• pub fn rank(prefixes, permutation): return k such that permutation == unrank(n,k), in $O(\frac{1}{2}n^3 + n)$ time.

  • replacing reset_permutation() with precomp_digit() ought to be easy, but I haven't done it yet.
    • Should also use the same trick as in unrank_precomp() and see if we can get this to run in $O(n^2)$ too.
  • python: heaps.py:HeapUnranker.rank(self, n, P)

• pub fn rank_noprecomp(permutation): return k such that permutation == unrank(permutation.len(),k), in $O(\frac{1}{2}n^2)$ (amortized, with i32 operations for the even branch). Without precomputed prefix tables.

• tests/oeis.rs: Calculations related to OEIS A280318 in time less than $O(n!)$

  • check_oeis_table_5040(): a(n) for an arbitrary n.
  • rank_example_for_n_4(): Finding n given a(n), using rank().

The implementations in this repo work on the indices. Whenever you're asked to provide a "permutation", you're being asked for a list of transposition indices. Example: If you want to unrank the final output of Heap's algorithm given a base array of [r,g,b], you'd call unrank(3, 5 /* 0-indexed */) and receive [2,1,0], and you'd then have to translate [r,g,b][x] for x in [2,1,0] to [b,g,r] yourself.

Missing

• What's currently missing from this repo is an efficient algorithm for job splitting, computing either k spans or, probably more interesting, factoradic spans to cover $$k \in 0 .. \text{factorial}(n) - 1$$ for a given number of partitions.

• Once we have used unrank() to get a permutation, we also need to recover the internal state used by Heap's algorithm in order to continue the sequence.

  • see lib.rs:heaps_state_at_k(n,k)

References

• Wikipedia on Heap's algorithm
• Stackexchange explanation of the problem we're solving
• Discussion thread on skipping prefixes, 2023 answer by Pseudonym♦
• Ruslan Ledesma-Garza's article about Heap's Algorithm
• Permutations by Interchanges, B.R. Heap 1963
• Knuth volume 4A: section 7.2.1.2: Generating all permutations
  • "Bypassing unwanted blocks", see the part where Knuth talks about Heap's algorithm being a special case of "Algorithm G"
  • essentially rank() corresponds to converting k to step G1, and executing step G4, with unrank() is being the inverse
• Factoradic / Factorial number system

References (other algorithms)

• More on permutation generation methods, Lipski, 1979
• Ranking and unranking permutations in linear time, Myrvold & Ruskey, 2000
• Unranking permutations in transposition order and linear time, Konstantinos A. Blekos
  • This paper is pretty sparse, but it is interesting because its permutations also only differ by one swap per output. It seems like it's an open problem to derive a Heaps' algorithm-like imperative implementation that efficiently steps through these permutations, at least I couldn't find one. But if it can be made to run as fast as Heap's algorithm, the $O(n)$ complexity of the unranking would make this permutation order preferable to Heap's algorithm. Exercise for the reader. :-)
• Generation of Permutations by Transposition, Mark B. Wells, August 1960
• Permutation Enumeration: Four new permutation algorithms, F.M. Ives, 1976 (with PL/I implementations!)
• A Unified Framework to Discover Permutation Generation Algorithms, Ganapath & Chowdhury, 2021
• Strictly In-Place Algorithms for Permuting and Inverting Permutations, Dudek & Gawrychowski & Pokorski, 2021
• Efficient Algorithms to Rank and Unrank Permutations in Lexicographic Order, Bonet