This ES5-compatible Node.js module/package exports functions (and a test) providing transformations between three equivalent permutation representations:
- p: Permutation of builtin ints incrementing from 0 (uints), like
[2, 0, 1] - a: mixed-radix (factorial number system) builtins Array (
[1, 1](base 2, 3)) - n: uint permutation Number (builtin or bigint) (
742(in base 10))
p's have a minimum length of 2. a's have a minimum length of 1.
The four functions that involve Numbers (pton, aton, ntop, and ntoa) accept functions for handling bigint objects of the user's choice. Note that JavaScript uints lose precision when greater than Math.pow(2, 53) (9007199254740992), which is between 18! (6402373705728000) and 19!.
The two functions that return a permutation (atop and ntop) can alternatively permute (Fisher-Yates-Knuth shuffle) existing arrays in place.
Except as documented, Factoradic functions don't mutate their arguments.
Uncomment the first line in index.js to make it browser compatible...meaning you can load the functions into an exports object in a developer console and play around; I don't know your bundler.
ptoa(p) -> a (source) takes a Permutation p and returns its corresponding Array a.
p may be modified. To pass in a copy, consider Array.prototype.slice.
Example: ptoa([1, 0]) // [1]
pton(p[, zero, muladd]) -> n (source) takes a Permutation p and returns its corresponding Number n. To make the return value a bigint, the bigint type's zero value zero and a multiply-add function muladd like
function(N, m, a){return N*m + a;}
must be provided. N is a bigint that muladd is free to modify. m is a builtin uint between 2 and p.length, inclusive. a is a builtin uint less than m. A bigint must be returned.
p may be modified. To pass in a copy, consider Array.prototype.slice.
When muladd is needed, its implementation determines whether n and zero reference the same object and whether zero may be modified.
Example: pton([0, 1, 2]) // 0
atop(a[, p]) -> p' (source) takes an Array a and optional array p to modify (Fisher-Yates-Knuth shuffle) and returns their corresponding Permutation p'.
When provided, p refers to the same object as p'. To use a copy of p instead, consider Array.prototype.slice.
Examples:
atop([1]) // [1, 0]atop([1], ['a', 'b']) // ['b', 'a']
aton(a[, zero, muladd]) -> n (source) takes an Array a and returns its corresponding Number n. To make the return value a bigint, the bigint type's zero value zero and a multiply-add function muladd like
function(N, m, a){return N*m + a;}
must be provided. N is a bigint that muladd is free to modify. m is a builtin uint between 2 and a.length + 1, inclusive. a is a builtin uint less than m. A bigint must be returned.
When muladd is needed, its implementation determines whether n and zero reference the same object and whether zero may be modified.
Example: aton([1, 0]) // 1
ntop(n, maxRadix OR p[, divmod]) -> p' (source) takes a Number n and either the size maxRadix of the permutation it applies to or an array p to modify (Fisher-Yates-Knuth shuffle) and returns their corresponding Permutation p'. When n is a bigint, a combined integer division and modulus function divmod like
function(N, d){return {div:Math.floor(N/d), mod:N%d}}
must be provided. N is a bigint that divmod is free to modify. d is a builtin uint between 2 and (maxRadix OR p.length), inclusive. div's value must be a bigint. mod's value must be a builtin uint.
When divmod is needed, its implementation determines whether n may be modified.
If n is greater than its expected range, it wraps back into that range (see Examples).
When provided, p refers to the same object as p'. To use a copy of p instead, consider Array.prototype.slice.
Examples:
ntop(0, 2) // [0, 1](0is amongmaxRadix! = 2!permutations)ntop(7, 3) // [1, 0, 2](7wraps to1, amongmaxRadix! = 3!permutations)ntop(1, ['a', 'b', 'c']) // ['b', 'a', 'c'](usingp)ntop(4, 2, function(N, d){...}) // [0, 1](usingmaxRadix;4wraps to0)
ntoa(n, maxRadix[, divmod]) -> a (source) takes a Number n and the size maxRadix of the permutation it applies to and returns its corresponding Array a. When n is a bigint, a combined integer division and modulus function divmod like
function(N, d){return {div:Math.floor(N/d), mod:N%d}}
must be provided. N is a bigint that divmod is free to modify. d is a builtin uint between 2 and maxRadix, inclusive. div's value must be a bigint. mod's value must be a builtin uint.
When divmod is needed, its implementation determines whether n may be modified.
If n is greater than its expected range, it wraps back into that range (see Examples).
Examples:
ntoa(5, 4) // [1, 2, 0](5is among4! = 2 * 3 * 4permutations)ntoa(17, 3) // [1, 2](17wraps to5, among3! = 2 * 3permutations)
test([maxMaxRadix], [onpass], [onfail]) (source), used by test.js and npm test, tests that the transformations preserve permutation information. All arguments are optional. Placeholder arguments must be falsy.
maxMaxRadix defaults to 4, testing all 2! through 4! permutations.
onpass defaults to console.log('pass') to output when the test succeeds.
onfail defaults to console.error to output information to reproduce a bug.
A successful test returns 0 (like an exit code). Otherwise, the onfail information is returned.
Besides the wrapping support in ntop and ntoa, notice that 0 is equivalent to [0, 1] and ['a', 'b', 'c'], depending on use (p) or context (maxRadix).
atop shuffling starts with lower radices:
atop([1, 2])
can be split as the equivalent
atop([0, 2], atop([1, 0]))
but not as atop([1, 0], atop([0, 2])).
One reason for the particular choice of permutation-number bijection is the 'zero-extensibility property' (please tell me if you may know its actual name):
atop([1, 1], [1, 2, 3])//[2, 3, 1]atop([1, 1, 0, 0], [1, 2, 3, 4, 5])//[2, 3, 1, 4, 5]
The facts that 4 and 5 are untouched and 1-3's new order is independent of maximum radix are analogous to a finite number's implicit leading zeroes.