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

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

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 whereSource

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.

Get the size of a permutation.

newPermute :: Int -> m pSource

Create a new permutation initialized to be the identity.

newPermute_ :: Int -> m pSource

Allocate a new permutation but do not initialize it.

unsafeGetElem :: p -> Int -> m IntSource

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 PermuteSource

unsafeThaw :: Permute -> m pSource

# Constructing mutable permutations

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

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 pSource

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 pSource

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 pSource

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 IntSource

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

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

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 BoolSource

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

getPeriod :: MPermute p m => p -> m IntegerSource

`getPeriod p`

- The first power of `p`

that is the identity permutation

# Permutation functions

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

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 BoolSource

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 BoolSource

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 pSource

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

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

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

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