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
- 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 ()
- swapElems :: MPermute p m => p -> Int -> Int -> m ()
- isValid :: MPermute p m => p -> m Bool
- 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)]
- 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
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
.
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.
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]
.
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.
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