permutation-0.5.0.5: A library for permutations and combinations.

Data.Permute

Description

Immutable permutations.

Synopsis

# Permutations

data Permute Source

The immutable permutation data type. Internally, a permutation of size `n` is stored as an `0`-based array of `n` `Int`s. The permutation represents a reordering of the integers `0, ..., (n-1)`. The permutation sents the value p[i] to `i`.

Instances

 Eq Permute Show Permute

# Creating permutations

Construct an identity permutation of the given size.

listPermute :: Int -> [Int] -> Permute Source

Construct a permutation from a list of elements. `listPermute n is` creates a permutation of size `n` with the `i`th element equal to `is !! i`. For the permutation to be valid, the list `is` must have length `n` and contain the indices `0..(n-1)` exactly once each.

swapsPermute :: Int -> [(Int, Int)] -> Permute Source

Construct a permutation from a list of swaps. `swapsPermute n ss` creats a permutation of size `n` given by a sequence of swaps. If `ss` is `[(i0,j0), (i1,j1), ..., (ik,jk)]`, the sequence of swaps is `i0 <-> j0`, then `i1 <-> j1`, and so on until `ik <-> jk`.

cyclesPermute :: Int -> [[Int]] -> Permute Source

Construct a permutation from a list of disjoint cycles. `cyclesPermute n cs` creates a permutation of size `n` which is the composition of the cycles `cs`.

# Accessing permutation elements

at :: Permute -> Int -> Int Source

`at p i` gets the value of the `i`th element of the permutation `p`. The index `i` must be in the range `0..(n-1)`, where `n` is the size of the permutation.

`indexOf p x` gets an index `i` such that `at p i` equals `x`.

# Permutation properties

Get the size of the permutation.

elems :: Permute -> [Int] Source

Get a list of the permutation elements.

Whether or not the permutation is made from an even number of swaps

`period p` - The first power of `p` that is the identity permutation

# Permutation functions

Get the inverse of a permutation.

Return the next permutation in lexicographic order, or `Nothing` if there are no further permutations. Starting with the identity permutation and repeatedly calling this function will iterate through all permutations of a given order.

Return the previous permutation in lexicographic order, or `Nothing` if no such permutation exists.

# Applying permutations

swaps :: Permute -> [(Int, Int)] Source

Get a list of swaps equivalent to the permutation. A result of `[ (i0,j0), (i1,j1), ..., (ik,jk) ]` means swap `i0 <-> j0`, then `i1 <-> j1`, and so on until `ik <-> jk`.

invSwaps :: Permute -> [(Int, Int)] Source

Get a list of swaps equivalent to the inverse of permutation.

cycleFrom :: Permute -> Int -> [Int] Source

`cycleFrom p i` gets the list of elements reachable from `i` by repeated application of `p`.

cycles :: Permute -> [[Int]] Source

`cycles p` returns the list of disjoin cycles in `p`.

# Sorting

sort :: Ord a => Int -> [a] -> ([a], Permute) Source

`sort n xs` sorts the first `n` elements of `xs` and returns a permutation which transforms `xs` into sorted order. The results are undefined if `n` is greater than the length of `xs`. This is a special case of `sortBy`.

sortBy :: (a -> a -> Ordering) -> Int -> [a] -> ([a], Permute) Source

order :: Ord a => Int -> [a] -> Permute Source

`order n xs` returns a permutation which rearranges the first `n` elements of `xs` into ascending order. The results are undefined if `n` is greater than the length of `xs`. This is a special case of `orderBy`.

orderBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute Source

rank :: Ord a => Int -> [a] -> Permute Source

`rank n xs` eturns a permutation, the inverse of which rearranges the first `n` elements of `xs` into ascending order. The returned permutation, `p`, has the property that `p[i]` is the rank of the `i`th element of `xs`. The results are undefined if `n` is greater than the length of `xs`. This is a special case of `rankBy`.

rankBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute Source