Stability | experimental |
---|---|

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

Immutable permutations.

- data Permute
- permute :: Int -> Permute
- listPermute :: Int -> [Int] -> Permute
- swapsPermute :: Int -> [(Int, Int)] -> Permute
- apply :: Permute -> Int -> Int
- unsafeApply :: Permute -> Int -> Int
- size :: Permute -> Int
- elems :: Permute -> [Int]
- inverse :: Permute -> Permute
- next :: Permute -> Maybe Permute
- prev :: Permute -> Maybe Permute
- swaps :: Permute -> [(Int, Int)]
- invSwaps :: Permute -> [(Int, 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 `i`

th element of the array stores
the value `p[i]`

.

# Creating permutations

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.

unsafeApply :: Permute -> Int -> IntSource

# Permutation properties

# Permutation functions

next :: Permute -> Maybe PermuteSource

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 PermuteSource

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`

.

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`

.

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`

.