| Copyright | Copyright (c) Patrick Perry <patperry@stanford.edu> |
|---|---|
| License | BSD3 |
| Maintainer | Patrick Perry <patperry@stanford.edu> |
| Stability | experimental |
| Safe Haskell | None |
| Language | Haskell98 |
Data.Permute.MPermute
Contents
Description
An overloaded interface to mutable permutations. For permutation types which can be used with this interface, see Data.Permute.IO and Data.Permute.ST.
Synopsis
- class Monad m => MPermute p m | p -> m, m -> p
- newPermute :: MPermute p m => Int -> m p
- newPermute_ :: MPermute p m => Int -> 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 ()
- getSize :: MPermute p m => p -> m Int
- getElems :: MPermute p m => p -> m [Int]
- setElems :: MPermute p m => p -> [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
- unsafeFreeze :: MPermute p m => p -> m Permute
- thaw :: MPermute p m => Permute -> m p
- unsafeThaw :: 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
- unsafeGetElem :: MPermute p m => p -> Int -> m Int
- unsafeSetElem :: MPermute p m => p -> Int -> Int -> m ()
- unsafeSwapElems :: MPermute p m => p -> Int -> Int -> m ()
Class of mutable permutation types
class Monad m => MPermute p m | p -> m, m -> p 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.
Minimal complete definition
getSize, newPermute, newPermute_, unsafeGetElem, unsafeSetElem, unsafeSwapElems, getElems, setElems, unsafeFreeze, unsafeThaw, unsafeInterleaveM
Instances
Constructing mutable permutations
newPermute :: MPermute p m => Int -> m p Source #
Create a new permutation initialized to be the identity.
newPermute_ :: MPermute p m => Int -> m p Source #
Allocate a new permutation but do not initialize it.
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 ith 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 ith 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 ith 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 ith and jth elements of the
permutation p.
Permutation properties
getElems :: MPermute p m => 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 :: MPermute p m => p -> [Int] -> m () Source #
Set all the values of a permutation from a list of elements.
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.
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 ith 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
unsafeFreeze :: MPermute p m => p -> m Permute Source #
unsafeThaw :: MPermute p m => Permute -> m p Source #