permutation-0.5.0.5: A library for permutations and combinations.

CopyrightCopyright (c) Patrick Perry <patperry@stanford.edu>
LicenseBSD3
MaintainerPatrick Perry <patperry@stanford.edu>
Stabilityexperimental
Safe HaskellNone
LanguageHaskell98

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 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 #

Constructing mutable permutations

newPermute :: MPermute p m => Int -> m p #

Create a new permutation initialized to be the identity.

newPermute_ :: MPermute p m => Int -> m p #

Allocate a new permutation but do not initialize it.

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

getSize :: MPermute p m => p -> m Int #

Get the size of a permutation.

getElems :: MPermute p m => 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 :: MPermute p m => p -> [Int] -> m () #

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

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.

unsafeFreeze :: MPermute p m => p -> m Permute #

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

Convert an immutable permutation to a mutable one.

unsafeThaw :: MPermute p m => Permute -> m p #

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 #

unsafeGetElem :: MPermute p m => p -> Int -> m Int #

unsafeSetElem :: MPermute p m => p -> Int -> Int -> m () #

unsafeSwapElems :: MPermute p m => p -> Int -> Int -> m () #