Superpermute

This module incrementally generates superpermutations of arbitrarily-sized sets of symbols, one symbol at a time. Because the superpermutation is generated incrementally, and earlier portions do not need to be retained to calculate remaining symbols, memory consumption is linear in the cardinality of the symbol set, not the (factorially larger) size of the superpermutation. Additionally, all data structures are allocated up-front, minimizing memory management overhead and GC pauses.

Up to permutations of order 6, hard-coded index sequences are used for maximum efficiency. For orders 5 and below, the outputs are known to be of optimal length.

Above order 6, superpermutations are generated according to Aaron Williams's graph construction, described in Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2). Incremental graph traversal is accomplished using the local edge selection rules described by Greg Egan.

The code is heavily commented in the hopes that it will be a useful reference for understanding the superpermutation algorithm, as well as being highly performant.

The module exports the following functions:

function superperm_length(n: number): bigint;
function superpermute(n: number, cycle?: boolean): Generator<number>;
function superpermute<T>(symbols: T[], cycle?: boolean): Generator<T>;

superperm_length(n) is a convenience function which calculates the length of superpermutation which will be produced for a symbol set of size n. This is considerably faster than counting the elements of the superpermutation as they are produced, and may be used to verify the correctness of the generator, pre-allocate memory, etc.

The primary superpermute function has two overloads. superpermute(n: number, cycle?: boolean) implicitly uses the integers from 1 to n, inclusive, as the set to permute, and always begins with the increasing sequence 1..n. superpermute<T>(symbols: T[], cycle?: boolean) instead allows the user to supply an arbitrary array of symbols to permute, and initially yields symbols in the same order they are given in the input.

In each case, the second, optional, argument defaults to false, meaning that the generator will terminate when a complete superpermutation has been produced. If cycle is instead set to true, symbols will be produced indefinitely, with the same sequence repeating in a cyclic fashion.