Permutation Arrays

June 30, 2014

While working on March, I started thinking about the tradeoff between array access and insertion. An array gives us constant-time indexed access, but inserting into its middle requires shifting the following elements. A linked list avoids that shift once we have the insertion point, but finding an element by index takes a walk through the list.

Could we leave the elements in their storage slots and change only their logical order?

A separate array of offsets would do that, but inserting into the offset array still requires shifting entries. What if we encoded the entire ordering as a single number instead?

A number for every order

Three storage slots have six possible arrangements. A permutation rank assigns an integer to each arrangement. Different rankings are possible; the one that interests me is the Steinhaus–Johnson–Trotter ordering:

Consecutive ranks differ by one adjacent swap. If physical storage contains [A, B, C], rank 1 makes the logical sequence [A, C, B] without changing which slot holds each value.

The number grows large, of course. There are n! permutations, so encoding every possible order requires ceil(log2(n!)) bits. For 50 elements that is 215 bits; for 1,024 elements, 8,770 bits. The number of arrangements grows factorially, but the number of bits grows as Θ(n log n).

That does not rule the idea out. It does mean that arithmetic on the rank cannot be treated as constant-time for arbitrarily large collections.

Insertion has a useful shortcut

The SJT ordering builds permutations recursively. For each ordering of n elements, the new largest element travels through all n + 1 positions. Its direction alternates between successive blocks.

This gives us a particularly nice operation. Allocate a new slot numbered n, then insert it at logical position p, counting from zero. If the old rank is r, the new rank is:

if r is even:
    new_rank = (n + 1) * r + (n - p)
else:
    new_rank = (n + 1) * r + p

For example, [A, C, B] has slot order [0, 2, 1] and rank 1. Append D to physical storage, then insert it at logical position 1:

physical slots: [A, B, C, D]
new rank:      4 * 1 + 1 = 5
logical order: [0, 3, 2, 1]
logical values: [A, D, C, B]

No existing value needs a different slot number. The rank update takes a constant number of big-integer operations, although their cost grows with the rank’s size. Allocating storage is a separate concern.

There is a matching shortcut for removing the highest-numbered slot: for a permutation of size n, its removal leaves rank floor(r / n). These shortcuts work for the newly allocated, largest slot. They do not automatically solve arbitrary deletion or reuse of old slots.

The catch is access

Adding one to an SJT rank performs an adjacent swap, but an arbitrary adjacent swap need not change the rank by one. In the table above, swapping the first two slots of rank 0 produces rank 5. We cannot implement every rearrangement by simply adding its distance to the rank.

We can, however, resolve an index without enumerating all the preceding permutations—or even constructing the full permutation. At size n, divide the rank:

q, d = divmod(r, n)
position = n - 1 - d if q is even, otherwise d

This identifies the position of slot n - 1. If that is our requested index, we have the answer. Otherwise, remove that position conceptually: decrement the requested index if it lies to the right, replace r with q, and continue at size n - 1.

The procedure works, but takes up to n divisions. Looking up slot 0 in the identity ordering reaches every level. It avoids materializing the permutation, but does not deliver logarithmic random access.

Ranking and unranking are established problems. Myrvold and Ruskey describe algorithms using O(n) arithmetic operations for a different ordering. That is useful context, but does not establish constant-time edits or logarithmic indexed lookup for this representation.

Putting it to work

A small Python prototype verifies the rank formulas against an independent SJT generator for every permutation through eight elements. It also checks indexed lookup and mixed insertions and deletions against an ordinary list.

For general deletion, the prototype marks a slot unused and keeps it in the encoded permutation. The remaining values retain their slot numbers, but lookup must skip unused entries. Insertion must also translate a logical position into a position among all allocated slots. The simple implementation decodes the permutation to do that; its list-based decoding has quadratic worst-case work. Unused trailing slots can be reclaimed, but interior holes remain encoded. Storage and rank size therefore follow allocated slots rather than just the live element count.

So this is not yet the perfect general-purpose collection. The experiment establishes a compact ordering representation, a useful insertion formula, and an access algorithm whose limitations we can measure. It does not prove that a better algorithm is impossible.

For the small stacks that prompted the idea, that may still be worth exploring. Once the stack size is bounded, a permutation rank could fit in a machine word, and precomputed mappings could make rearrangement and lookup inexpensive. The question becomes where that approach pays for its tables and arithmetic—and where an ordinary array is simply better.

Implementations and measurements

The Permarray project contains Python and Rust implementations, verification programs, and benchmark methodology and results. The Rust version keeps its rank in a u128, limiting it to 34 allocated slots. That bounded case makes machine-integer operations practical, while leaving the indexed-lookup work and hole handling visible.

A benchmark snapshot from November 2, 2026 shows the trade-off. With 32 existing inline 4 KiB values, inserting in the middle and removing that newest value took about 158 ns for Permarray, versus 1,371 ns for a vector of values and 214 ns for a vector of offsets into stable storage. In a separate indexed-lookup workload with 8-byte values, Permarray took about 64 ns versus 1.3 ns for either vector alternative.

Those are deliberately narrow workloads, with preallocated hot storage and no accumulating holes. The edit benchmark uses the favorable newest-slot removal shortcut. It shows a case worth investigating, not a general win for arbitrary insertion and deletion. The pure-Python version was slower than Python’s built-in lists in the measured workloads.

← Selected writing · Older writing