A permutation. Internally it is an (unboxed) array of the integers [1..n], with indexing range also being (1,n).

If this array of integers is [p1,p2,...,pn], then in two-line notations, that represents the permutation

( 1  2  3  ... n  )
( p1 p2 p3 ... pn )

That is, it is the permutation sigma whose (right) action on the set [1..n] is

sigma(1) = p1
sigma(2) = p2 
...

(NOTE: this changed at version 0.2.8.0!)

Note: this is slower than permutationUArray

Note: Indexing starts from 1.

Checks whether the input is a permutation of the numbers [1..n].

Checks whether the input is a permutation of the numbers [1..n].

Checks the input.

Assumes that the input is a permutation of the numbers [1..n].

Returns n, where the input is a permutation of the numbers [1..n]

Disjoint cycle notation for permutations. Internally it is [[Int]].

The cycles are to be understood as follows: a cycle [c1,c2,...,ck] means the permutation

( c1 c2 c3 ... ck )
( c2 c3 c4 ... c1 )

Convert to disjoint cycle notation.

This is compatible with Maple's convert(perm,'disjcyc') and also with Mathematica's PermutationCycles[perm]

Note however, that for example Mathematica uses the top row to represent a permutation, while we use the bottom row - thus even though this function looks identical, the meaning of both the input and output is different!

Checks whether the permutation is the identity permutation

Checks whether the permutation is the reverse permutation @[n,n-1,n-2,...,2,1].

Plus 1 or minus 1.

A transposition (swapping two elements).

transposition n (i,j) is the permutation of size n which swaps i'th and j'th elements.

Product of transpositions.

transpositions n list == multiplyMany [ transposition n pair | pair <- list ]

adjacentTransposition n k swaps the elements k and (k+1).

Product of adjacent transpositions.

adjacentTranspositions n list == multiplyMany [ adjacentTransposition n idx | idx <- list ]

The permutation which cycles a list left by one step:

permuteList (cycleLeft 5) "abcde" == "bcdea"

Or in two-line notation:

( 1 2 3 4 5 )
( 2 3 4 5 1 )

The permutation which cycles a list right by one step:

permuteList (cycleRight 5) "abcde" == "eabcd"

Or in two-line notation:

( 1 2 3 4 5 )
( 5 1 2 3 4 )

The permutation [n,n-1,n-2,...,2,1]. Note that it is the inverse of itself.

An inversion of a permutation sigma is a pair (i,j) such that i<j and sigma(i) > sigma(j).

This functions returns the inversion of a permutation.

Returns the number of inversions:

numberOfInversions perm = length (inversions perm)

Synonym for numberOfInversionsMerge

Returns the number of inversions, using the definition, thus it's O(n^2).

Returns the number of inversions, using the merge-sort algorithm. This should be O(n*log(n))

Bubble sorts breaks a permutation into the product of adjacent transpositions:

multiplyMany' n (map (transposition n) $ bubbleSort2 perm) == perm

Note that while this is not unique, the number of transpositions equals the number of inversions.

Another version of bubble sort. An entry i in the return sequence means the transposition (i,i+1):

multiplyMany' n (map (adjacentTransposition n) $ bubbleSort perm) == perm

The identity (or trivial) permutation.

The inverse permutation.

Multiplies two permutations together: p multiply q means the permutation when we first apply p, and then q (that is, the natural action is the right action)

See also permute for our conventions.

Multiply together a non-empty list of permutations (the reason for requiring the list to be non-empty is that we don't know the size of the result). See also multiplyMany'.

Multiply together a (possibly empty) list of permutations, all of which has size n

Right action of a permutation on a set. If our permutation is encoded with the sequence [p1,p2,...,pn], then in the two-line notation we have

( 1  2  3  ... n  )
( p1 p2 p3 ... pn )

We adopt the convention that permutations act on the right (as in Knuth):

permute pi2 (permute pi1 set) == permute (pi1 `multiply` pi2) set

Synonym to permuteRight

Right action on lists. Synonym to permuteListRight

The left (opposite) action of the permutation group.

permuteLeft pi2 (permuteLeft pi1 set) == permuteLeft (pi2 `multiply` pi1) set

It is related to permuteLeft via:

permuteLeft  pi arr == permuteRight (inverse pi) arr
permuteRight pi arr == permuteLeft  (inverse pi) arr

The right (standard) action of permutations on sets.

permuteRight pi2 (permuteRight pi1 set) == permuteRight (pi1 `multiply` pi2) set

The second argument should be an array with bounds (1,n). The function checks the array bounds.

The left (opposite) action on a list. The list should be of length n.

permuteLeftList perm set == permuteList (inverse perm) set
fromPermutation (inverse perm) == permuteLeftList perm [1..n]

The right (standard) action on a list. The list should be of length n.

fromPermutation perm == permuteRightList perm [1..n]

Synonym for twoLineNotation

The standard two-line notation, moving the element indexed by the top row into the place indexed by the corresponding element in the bottom row.

The inverse two-line notation, where the it's the bottom line which is in standard order. The columns of this are a permutation of the columns twoLineNotation.

Remark: the top row of inverseTwoLineNotation perm is the same as the bottom row of twoLineNotation (inverse perm).

Two-line notation for any set of numbers

A synonym for permutationsNaive

All permutations of [1..n] in lexicographic order, naive algorithm.

# = n!

A synonym for randomPermutationDurstenfeld.

A synonym for randomCyclicPermutationSattolo.

Generates a uniformly random permutation of [1..n]. Durstenfeld's algorithm (see http://en.wikipedia.org/wiki/Knuth_shuffle).

Generates a uniformly random cyclic permutation of [1..n]. Sattolo's algorithm (see http://en.wikipedia.org/wiki/Knuth_shuffle).

Generates all permutations of a multiset. The order is lexicographic. A synonym for fasc2B_algorithm_L

# = \frac { (sum_i n_i) ! } { \prod_i (n_i !) }

Generates all permutations of a multiset (based on "algorithm L" in Knuth; somewhat less efficient). The order is lexicographic.