Copyright | Copyright (c) , Patrick Perry <patperry@stanford.edu> |
---|---|

License | BSD3 |

Maintainer | Patrick Perry <patperry@stanford.edu> |

Stability | experimental |

Safe Haskell | None |

Language | Haskell98 |

Immutable permutations.

- data Permute
- permute :: Int -> Permute
- listPermute :: Int -> [Int] -> Permute
- swapsPermute :: Int -> [(Int, Int)] -> Permute
- cyclesPermute :: Int -> [[Int]] -> Permute
- at :: Permute -> Int -> Int
- unsafeAt :: Permute -> Int -> Int
- indexOf :: Permute -> Int -> Int
- size :: Permute -> Int
- elems :: Permute -> [Int]
- isEven :: Permute -> Bool
- period :: Permute -> Integer
- inverse :: Permute -> Permute
- next :: Permute -> Maybe Permute
- prev :: Permute -> Maybe Permute
- swaps :: Permute -> [(Int, Int)]
- invSwaps :: Permute -> [(Int, Int)]
- cycleFrom :: Permute -> Int -> [Int]
- cycles :: Permute -> [[Int]]
- sort :: Ord a => Int -> [a] -> ([a], Permute)
- sortBy :: (a -> a -> Ordering) -> Int -> [a] -> ([a], Permute)
- order :: Ord a => Int -> [a] -> Permute
- orderBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute
- rank :: Ord a => Int -> [a] -> Permute
- rankBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute

# Permutations

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`

.

# Creating permutations

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.

# Permutation properties

# Permutation functions

next :: Permute -> Maybe Permute Source

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.

prev :: Permute -> Maybe Permute Source

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`

.

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

.

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`

.

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`

.