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

License | BSD3 |

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

Stability | experimental |

Safe Haskell | None |

Language | Haskell98 |

An overloaded interface to mutable permutations. For permutation types which can be used with this interface, see Data.Permute.IO and Data.Permute.ST.

- class Monad m => MPermute p m | p -> m, m -> p where
- getSize :: p -> m Int
- newPermute :: Int -> m p
- newPermute_ :: Int -> m p
- unsafeGetElem :: p -> Int -> m Int
- unsafeSetElem :: p -> Int -> Int -> m ()
- unsafeSwapElems :: p -> Int -> Int -> m ()
- getElems :: p -> m [Int]
- setElems :: p -> [Int] -> m ()
- unsafeFreeze :: p -> m Permute
- unsafeThaw :: Permute -> m p

- newListPermute :: MPermute p m => Int -> [Int] -> m p
- newSwapsPermute :: MPermute p m => Int -> [(Int, Int)] -> m p
- newCyclesPermute :: MPermute p m => Int -> [[Int]] -> m p
- newCopyPermute :: MPermute p m => p -> m p
- copyPermute :: MPermute p m => p -> p -> m ()
- setIdentity :: MPermute p m => p -> m ()
- getElem :: MPermute p m => p -> Int -> m Int
- setElem :: MPermute p m => p -> Int -> Int -> m ()
- getIndexOf :: MPermute p m => p -> Int -> m Int
- swapElems :: MPermute p m => p -> Int -> Int -> m ()
- isValid :: MPermute p m => p -> m Bool
- getIsEven :: MPermute p m => p -> m Bool
- getPeriod :: MPermute p m => p -> m Integer
- getInverse :: MPermute p m => p -> m p
- copyInverse :: MPermute p m => p -> p -> m ()
- setNext :: MPermute p m => p -> m Bool
- setPrev :: MPermute p m => p -> m Bool
- getSwaps :: MPermute p m => p -> m [(Int, Int)]
- getInvSwaps :: MPermute p m => p -> m [(Int, Int)]
- getCycleFrom :: MPermute p m => p -> Int -> m [Int]
- getCycles :: MPermute p m => p -> m [[Int]]
- getSort :: (Ord a, MPermute p m) => Int -> [a] -> m ([a], p)
- getSortBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m ([a], p)
- getOrder :: (Ord a, MPermute p m) => Int -> [a] -> m p
- getOrderBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m p
- getRank :: (Ord a, MPermute p m) => Int -> [a] -> m p
- getRankBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m p
- freeze :: MPermute p m => p -> m Permute
- thaw :: MPermute p m => Permute -> m p
- unsafeNewListPermute :: MPermute p m => Int -> [Int] -> m p
- unsafeNewSwapsPermute :: MPermute p m => Int -> [(Int, Int)] -> m p
- unsafeNewCyclesPermute :: MPermute p m => Int -> [[Int]] -> m p

# Class of mutable permutation types

class Monad m => MPermute p m | p -> m, m -> p where Source

Class for representing a mutable permutation. The type is parameterized
over the type of the monad, `m`

, in which the mutable permutation will be
manipulated.

getSize, newPermute, newPermute_, unsafeGetElem, unsafeSetElem, unsafeSwapElems, getElems, setElems, unsafeFreeze, unsafeThaw, unsafeInterleaveM

Get the size of a permutation.

newPermute :: Int -> m p Source

Create a new permutation initialized to be the identity.

newPermute_ :: Int -> m p Source

Allocate a new permutation but do not initialize it.

unsafeGetElem :: p -> Int -> m Int Source

unsafeSetElem :: p -> Int -> Int -> m () Source

unsafeSwapElems :: p -> Int -> Int -> m () Source

getElems :: p -> m [Int] Source

Get a lazy list of the permutation elements. The laziness makes this function slightly dangerous if you are modifying the permutation.

setElems :: p -> [Int] -> m () Source

Set all the values of a permutation from a list of elements.

unsafeFreeze :: p -> m Permute Source

unsafeThaw :: Permute -> m p Source

# Constructing mutable permutations

newListPermute :: MPermute p m => Int -> [Int] -> m p Source

Construct a permutation from a list of elements.
`newListPermute 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.

newSwapsPermute :: MPermute p m => Int -> [(Int, Int)] -> m p Source

Construct a permutation from a list of swaps.
`newSwapsPermute n ss`

creates a permutation of size `n`

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

.

newCyclesPermute :: MPermute p m => Int -> [[Int]] -> m p Source

Construct a permutation from a list of disjoint cycles.
`newCyclesPermute n cs`

creates a permutation of size `n`

which is the
composition of the cycles `cs`

.

newCopyPermute :: MPermute p m => p -> m p Source

Construct a new permutation by copying another.

copyPermute :: MPermute p m => p -> p -> m () Source

`copyPermute dst src`

copies the elements of the permutation `src`

into the permutation `dst`

. The two permutations must have the same
size.

setIdentity :: MPermute p m => p -> m () Source

Set a permutation to the identity.

# Accessing permutation elements

getElem :: MPermute p m => p -> Int -> m Int Source

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

setElem :: MPermute p m => p -> Int -> Int -> m () Source

`setElem p i x`

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

getIndexOf :: MPermute p m => p -> Int -> m Int Source

`getIndexOf p x`

returns `i`

sutch that `getElem p i`

equals `x`

. This
is a linear-time operation.

swapElems :: MPermute p m => p -> Int -> Int -> m () Source

`swapElems p i j`

exchanges the `i`

th and `j`

th elements of the
permutation `p`

.

# Permutation properties

isValid :: MPermute p m => p -> m Bool Source

Returns whether or not the permutation is valid. For it to be valid,
the numbers `0,...,(n-1)`

must all appear exactly once in the stored
values `p[0],...,p[n-1]`

.

getIsEven :: MPermute p m => p -> m Bool Source

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

getPeriod :: MPermute p m => p -> m Integer Source

`getPeriod p`

- The first power of `p`

that is the identity permutation

# Permutation functions

getInverse :: MPermute p m => p -> m p Source

Compute the inverse of a permutation.

copyInverse :: MPermute p m => p -> p -> m () Source

Set one permutation to be the inverse of another.
`copyInverse inv p`

computes the inverse of `p`

and stores it in `inv`

.
The two permutations must have the same size.

setNext :: MPermute p m => p -> m Bool Source

Advance a permutation to the next permutation in lexicogrphic order and
return `True`

. If no further permutaitons are available, return `False`

and
leave the permutation unmodified. Starting with the idendity permutation
and repeatedly calling `setNext`

will iterate through all permutations of a
given size.

setPrev :: MPermute p m => p -> m Bool Source

Step backwards to the previous permutation in lexicographic order and
return `True`

. If there is no previous permutation, return `False`

and
leave the permutation unmodified.

# Applying permutations

getSwaps :: MPermute p m => p -> m [(Int, Int)] Source

Get a lazy 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`

. The laziness makes this
function slightly dangerous if you are modifying the permutation.

getInvSwaps :: MPermute p m => p -> m [(Int, Int)] Source

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

getCycleFrom :: MPermute p m => p -> Int -> m [Int] Source

`getCycleFrom p i`

gets the list of elements reachable from `i`

by repeated application of `p`

.

getCycles :: MPermute p m => p -> m [[Int]] Source

`getCycles p`

returns the list of disjoin cycles in `p`

.

# Sorting

getSort :: (Ord a, MPermute p m) => Int -> [a] -> m ([a], p) Source

`getSort 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 `getSortBy`

.

getOrder :: (Ord a, MPermute p m) => Int -> [a] -> m p Source

`getOrder 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 `getOrderBy`

.

getOrderBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m p Source

getRank :: (Ord a, MPermute p m) => Int -> [a] -> m p Source

`getRank 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 `getRankBy`

.

# Converstions between mutable and immutable permutations

# Unsafe operations

unsafeNewListPermute :: MPermute p m => Int -> [Int] -> m p Source

unsafeNewCyclesPermute :: MPermute p m => Int -> [[Int]] -> m p Source