permutation-0.2.1: A library for representing and applying permutations.

Stability experimental Patrick Perry

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 `i`th element of the array stores the value `p[i]`.

Instances

 Eq Permute Show Permute

# Creating permutations

Construct an identity permutation of the given size.

listPermute :: Int -> [Int] -> PermuteSource

Construct a permutation from a list of elements. `listPermute n is` creates a permuation 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)] -> PermuteSource

Construct a permutation from a list of swaps. `swapsPermute n ss` creats a permuation 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`.

# Accessing permutation elements

apply :: Permute -> Int -> IntSource

`apply 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.

# Permutation properties

Get the size of the permutation.

elems :: Permute -> [Int]Source

Get a list of the permutation elements.

# 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 there is no such permutation.

# 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.

# 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] -> PermuteSource

`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] -> PermuteSource

rank :: Ord a => Int -> [a] -> PermuteSource

`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] -> PermuteSource