Function

Apply a given sequence (in the given order) of transpositions (given as index tuples) to the identity permutation over input n elements.

Returns a newly allocated array containing the bitreversal permutation for input n items. Note that n MUST be a power of 2.

Compose two input permutations. The resulting permutation is output as an array of indices.

Make a copy of the input permutation.

Computes a cycle decomposition of the input permutation. For a given input, the algorithm used will always yield the same cycle decomposition. See _cycles for implementation.

Returns the identity permutation of a given size.

Computes the inverse tau of the input permutation sigma, that is, the permutation such that compose(sigma, tau) returns identity(sigma.length). Alternatives include using _invertcycles and itranspositions.

Computes the sequence of transpositions that if applied to sigma result in invert(sigma). Uses _itranspositions as the underlying implementation.

Example:

const invert = sigma => apply( sigma.length , itranspositions( sigma ) ) ;

Computes the permutation that follows the input permutation. If the input permutation is the last for its elements, return the first for its elements. The input permutation is not altered.

Allocates a new permutation of given input size.

Generate all permutations on n elements.

Reverses input permutation in-place.

Outputs a new permutation that is the reverse of the input permutation.

Creates a copy of the input permutation, applies an input transpose, then returns the result.

Outputs the permutation on input n numbers that only transposes two input elements a and b.

Computes the transposition decomposition of the input permutation as an Iterator.

Generates an helper array of given size (used in _cycle, cycle).

Applies a given sequence (in the given order) of transpositions (given as index tuples) to a given permutation. The permutation is modified in-place.

Fills an input array with the bitreversal permutation for input n items. The array is filled starting at index 0 and ending at index n-1. Note that n MUST be a power of 2.

Compose two input permutations. The resulting permutation is output as an iterator of indices instead of an array of indices.

Copy an input permutation to an output array.

Computes a cycle decomposition of an input permutation. This algorithm is deterministic; the algorithm will procedes in a sequential manner, first yielding the cycle containing the first (in input order) index of the permutation, then yielding the cycle containing the first (in input order) index of the permutation that is not in the first cycle, etc. The output is in the form of an iterator over cycles [a, [b, c, ...]] where a is the first element of the cycle and the list [b, c, ...] contains the second, third, etc. elements of the cycle. The algorithm uses an helper array to remember which elements have already been encountered.

See:

• https://en.wikipedia.org/wiki/Permutation#Cycle_notation

Fills an input array with the identity permutation on input n elements.

Fills an input array with the inverse tau of the input permutation sigma, that is, the permutation such that compose(sigma, tau) returns identity(sigma.length). See invert for the higher level API.

Inverts given cycles in a given permutation in-place. Can be used as an alternative way of inverting an entire permutation by inverting all of its cycles in the identity permutation.

Example:

const invert = sigma => {
  const tau = identity( sigma.length ) ;
  const cycles_sigma = cycles( sigma ) ;
  _invertcycles( cycles_sigma , tau ) ;
  return tau ;
} ;

Computes the sequence of transpositions that if applied to sigma result in invert(sigma). Needs an helper array to keep track of processed elements. See itranspositions for higher level API.

Updates the input permutation to the next one in-place. Returns true unless the input permutation is the last for its elements. In that case, the input permutation remains untouched.

Yields all permutations starting from a given one and ending at the last permutation.

Reverses input permutation in-place from input index i (include) to input index j (excluded).

Transpose elements of input index a and b in the input permutation.

Helper method for transposition. Transposes a with b in sigma provided sigma[a] === a and sigma[b] === b.

Computes the transposition decomposition of some permutation given its cycle decomposition.

For a given size n, fills an input array with false. Starting at index 0, ending at index n-1. This array is used as a helper in other function. For example, for computing the cycle decomposition of an input permutation (see _cycles, cycles).