Data.Permute.MPermute

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 of mutable permutation types

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

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.

Methods

getSize :: p -> m Int

Get the size of a permutation.

newPermute :: Int -> m p

Create a new permutation initialized to be the identity.

newPermute_ :: Int -> m p

Allocate a new permutation but do not initialize it.

unsafeGetElem :: p -> Int -> m Int

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

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

getElems :: p -> m [Int]

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 ()

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

unsafeFreeze :: p -> m Permute

unsafeThaw :: Permute -> m p

Instances

MPermute IOPermute IO

MPermute (STPermute s) (ST s)

Constructing mutable permutations

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

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

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

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

Construct a new permutation by copying another.

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

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 ()

Set a permutation to the identity.

Accessing permutation elements

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

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 ()

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

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 ()

swapElems p i j exchanges the ith and jth elements of the permutation p.

Permutation properties

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

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

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

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

getPeriod p - The first power of p that is the identity permutation

Permutation functions

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

Compute the inverse of a permutation.

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

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

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

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)]

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)]

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

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

getCycleFrom p i gets the list of elements reachable from i by repeated application of p.

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

getCycles p returns the list of disjoin cycles in p.

Sorting

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

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.

getSortBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m ([a], p)

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

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

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

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.

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

Converstions between mutable and immutable permutations

freeze :: MPermute p m => p -> m Permute

Convert a mutable permutation to an immutable one.

thaw :: MPermute p m => Permute -> m p

Convert an immutable permutation to a mutable one.

Unsafe operations

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