-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | A library for permutations and combinations. -- @package permutation @version 0.5.0 -- | An overloaded interface to mutable permutations. For permutation types -- which can be used with this interface, see Data.Permute.IO and -- Data.Permute.ST. module Data.Permute.MPermute -- | 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. class Monad m => MPermute p m | p -> m, m -> p getSize :: MPermute p m => p -> m Int newPermute :: MPermute p m => Int -> m p newPermute_ :: MPermute p m => 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 () getElems :: MPermute p m => p -> m [Int] setElems :: MPermute p m => p -> [Int] -> m () unsafeFreeze :: MPermute p m => p -> m Permute unsafeThaw :: MPermute p m => Permute -> 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. newListPermute :: MPermute p m => 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. newSwapsPermute :: MPermute p m => Int -> [(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. newCyclesPermute :: MPermute p m => Int -> [[Int]] -> m p -- | Construct a new permutation by copying another. newCopyPermute :: MPermute p m => p -> m p -- | copyPermute dst src copies the elements of the permutation -- src into the permutation dst. The two permutations -- must have the same size. copyPermute :: MPermute p m => p -> p -> m () -- | Set a permutation to the identity. setIdentity :: MPermute p m => p -> m () -- | 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. getElem :: MPermute p m => p -> Int -> m Int -- | 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. setElem :: MPermute p m => p -> Int -> Int -> m () -- | getIndexOf p x returns i sutch that getElem p -- i equals x. This is a linear-time operation. getIndexOf :: MPermute p m => p -> Int -> m Int -- | swapElems p i j exchanges the ith and jth -- elements of the permutation p. swapElems :: MPermute p m => p -> Int -> Int -> m () -- | 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]. isValid :: MPermute p m => p -> m Bool -- | Whether or not the permutation is made from an even number of swaps getIsEven :: MPermute p m => p -> m Bool -- | getPeriod p - The first power of p that is the -- identity permutation getPeriod :: MPermute p m => p -> m Integer -- | Compute the inverse of a permutation. getInverse :: MPermute p m => p -> m p -- | 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. copyInverse :: MPermute p m => p -> p -> m () -- | 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. setNext :: 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. setPrev :: MPermute p m => p -> m Bool -- | 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. getSwaps :: MPermute p m => p -> m [(Int, Int)] -- | Get a lazy list of swaps equivalent to the inverse of a permutation. getInvSwaps :: MPermute p m => p -> m [(Int, Int)] -- | getCycleFrom p i gets the list of elements reachable from -- i by repeated application of p. getCycleFrom :: MPermute p m => p -> Int -> m [Int] -- | getCycles p returns the list of disjoin cycles in p. getCycles :: MPermute p m => p -> m [[Int]] -- | 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. getSort :: (Ord a, MPermute p m) => Int -> [a] -> m ([a], p) getSortBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m ([a], 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. getOrder :: (Ord a, MPermute p m) => Int -> [a] -> m p getOrderBy :: MPermute p m => (a -> a -> Ordering) -> 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. getRank :: (Ord a, MPermute p m) => Int -> [a] -> m p getRankBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m p -- | Convert a mutable permutation to an immutable one. freeze :: MPermute p m => p -> m Permute -- | Convert an immutable permutation to a mutable one. 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 instance MPermute IOPermute IO instance MPermute (STPermute s) (ST s) -- | Mutable permutations in the ST monad. module Data.Permute.ST -- | A mutable permutation that can be manipulated in the ST monad. -- The type argument s is the state variable argument for the -- ST type. data STPermute s -- | A safe way to create and work with a mutable permutation before -- returning an immutable one for later perusal. This function avoids -- copying the permutation before returning it - it uses unsafeFreeze -- internally, but this wrapper is a safe interface to that function. runSTPermute :: (forall s. ST s (STPermute s)) -> Permute -- | Mutable permutations in the IO monad. module Data.Permute.IO -- | A mutable permutation that can be manipulated in the IO monad. data IOPermute -- | Immutable permutations. module Data.Permute -- | The immutable permutation data type. Internally, a permutation of size -- n is stored as an 0-based array of n -- Ints. The permutation represents a reordering of the integers -- 0, ..., (n-1). The permutation sents the value p[i] to -- i. data Permute -- | Construct an identity permutation of the given size. permute :: Int -> Permute -- | Construct a permutation from a list of elements. listPermute 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. listPermute :: Int -> [Int] -> Permute -- | Construct a permutation from a list of swaps. swapsPermute n -- ss creats a permutation of size n given by 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. swapsPermute :: Int -> [(Int, Int)] -> Permute -- | Construct a permutation from a list of disjoint cycles. -- cyclesPermute n cs creates a permutation of size n -- which is the composition of the cycles cs. cyclesPermute :: Int -> [[Int]] -> Permute -- | at 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. at :: Permute -> Int -> Int unsafeAt :: Permute -> Int -> Int -- | indexOf p x gets an index i such that at p -- i equals x. indexOf :: Permute -> Int -> Int -- | Get the size of the permutation. size :: Permute -> Int -- | Get a list of the permutation elements. elems :: Permute -> [Int] -- | Whether or not the permutation is made from an even number of swaps isEven :: Permute -> Bool -- | period p - The first power of p that is the identity -- permutation period :: Permute -> Integer -- | Get the inverse of a permutation. inverse :: Permute -> Permute -- | Return the next permutation in lexicographic order, or -- Nothing if there are no further permutations. Starting with -- the identity permutation and repeatedly calling this function will -- iterate through all permutations of a given order. next :: Permute -> Maybe Permute -- | Return the previous permutation in lexicographic order, or -- Nothing if no such permutation exists. prev :: Permute -> Maybe Permute -- | Get a 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. swaps :: Permute -> [(Int, Int)] -- | Get a list of swaps equivalent to the inverse of permutation. invSwaps :: Permute -> [(Int, Int)] -- | cycleFrom p i gets the list of elements reachable from -- i by repeated application of p. cycleFrom :: Permute -> Int -> [Int] -- | cycles p returns the list of disjoin cycles in p. cycles :: Permute -> [[Int]] -- | sort 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 sortBy. sort :: Ord a => Int -> [a] -> ([a], Permute) sortBy :: (a -> a -> Ordering) -> Int -> [a] -> ([a], Permute) -- | order 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 orderBy. order :: Ord a => Int -> [a] -> Permute orderBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute -- | rank 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 rankBy. rank :: Ord a => Int -> [a] -> Permute rankBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute -- | An overloaded interface to mutable combinations. For combination types -- which can be used with this interface, see Data.Choose.IO and -- Data.Choose.ST. module Data.Choose.MChoose -- | Class for representing a mutable combination. The type is -- parameterized over the type of the monad, m, in which the -- mutable combination will be manipulated. class Monad m => MChoose c m | c -> m, m -> c getPossible :: MChoose c m => c -> m Int getSize :: MChoose c m => c -> m Int newChoose :: MChoose c m => Int -> Int -> m c newChoose_ :: MChoose c m => Int -> Int -> m c unsafeGetElem :: MChoose c m => c -> Int -> m Int unsafeSetElem :: MChoose c m => c -> Int -> Int -> m () getElems :: MChoose c m => c -> m [Int] setElems :: MChoose c m => c -> [Int] -> m () unsafeFreeze :: MChoose c m => c -> m Choose unsafeThaw :: MChoose c m => Choose -> m c -- | Construct a combination from a list of elements. newListChoose n k -- is creates a combination of k outcomes from n -- possibilities initialized to have the ith element equal to -- is !! i. For the combination to be valid, the elements must -- all be unique, they must be in sorted order, and they all must be in -- the range 0 .. n-1. newListChoose :: MChoose c m => Int -> Int -> [Int] -> m c -- | Construct a new combination by copying another. newCopyChoose :: MChoose c m => c -> m c -- | copyChoose dst src copies the elements of the combination -- src into the combination dst. The two combinations -- must have the same size. copyChoose :: MChoose c m => c -> c -> m () -- | Set a combination to be the first subset of its size. setFirst :: MChoose c m => c -> m () -- | getElem c i gets the value of the ith element of the -- combination c. The index i must be in the range -- 0..k-1, where n is the size of the combination. getElem :: MChoose c m => c -> Int -> m Int -- | setElem c i x sets the value of the ith element of -- the combination c. The index i must be in the range -- 0..k-1, where k is the size of the combination. setElem :: MChoose c m => c -> Int -> Int -> m () -- | Returns whether or not the combination is valid. For it to be valid, -- the elements must all be unique, they must be in sorted order, and -- they all must be in the range 0 .. n-1, where n is -- the number of possibilies in the combination. isValid :: MChoose c m => c -> m Bool -- | Compute the complement of a combination getComplement :: MChoose c m => c -> m c -- | Return a lazy list of the elements in the complement of a combination. -- If the combination is a subset of k outcomes from n -- possibilities, then the returned list will be sorted and of length -- n-k. Due to the laziness, you should be careful when using -- this function if you are also modifying the combination. getComplElems :: MChoose c m => c -> m [Int] -- | Advance a combination to the next in lexicogrphic order and return -- True. If no further combinations are available, return -- False and leave the combination unmodified. Starting with -- [ 0 .. k-1 ] and repeatedly calling setNext will -- iterate through all subsets of size k. setNext :: MChoose c m => c -> m Bool -- | Step backwards to the previous combination in lexicographic order and -- return True. If there is no previous combination, return -- False and leave the combination unmodified. setPrev :: MChoose c m => c -> m Bool -- | Convert a mutable combination to an immutable one. freeze :: MChoose c m => c -> m Choose -- | Convert an immutable combination to a mutable one. thaw :: MChoose c m => Choose -> m c unsafeNewListChoose :: MChoose c m => Int -> Int -> [Int] -> m c instance MChoose IOChoose IO instance MChoose (STChoose s) (ST s) -- | Mutable combinations in the ST monad. module Data.Choose.ST -- | A mutable combination that can be manipulated in the ST monad. -- The type argument s is the state variable argument for the -- ST type. data STChoose s -- | A safe way to create and work with a mutable combination before -- returning an immutable one for later perusal. This function avoids -- copying the combination before returning it - it uses unsafeFreeze -- internally, but this wrapper is a safe interface to that function. runSTChoose :: (forall s. ST s (STChoose s)) -> Choose -- | Mutable combinations in the IO monad. module Data.Choose.IO -- | A mutable combination that can be manipulated in the IO monad. data IOChoose -- | Immutable combinations. module Data.Choose -- | The immutable combination data type. A way of representing k -- unordered outcomes from n possiblities. The possibilites are -- represented as the indices 0, ..., n-1, and the outcomes are -- given as a subset of size k. The subset is stored with the -- indices in ascending order. data Choose -- | choose n k returns the first combination of k -- outcomes from n possibilites, namely the subset { 0, ..., -- k-1 }. choose :: Int -> Int -> Choose -- | Construct a combination from a list of elements. listChoose n k -- is creates a combination of k outcomes from n -- possibilities initialized to have the ith element equal to -- is !! i. For the combination to be valid, the elements must -- all be unique, they must be in sorted order, and they all must be in -- the range 0 .. n-1. listChoose :: Int -> Int -> [Int] -> Choose -- | at c i gets the value of the ith element of the -- combination c. The index i must be in the range -- 0..(k-1), where k is the size of the combination. at :: Choose -> Int -> Int unsafeAt :: Choose -> Int -> Int -- | Get the number of possibilities, n. possible :: Choose -> Int -- | Get the number of outcomes, k. size :: Choose -> Int -- | Get a list of the k outcomes. elems :: Choose -> [Int] -- | Get the inverse of a combination complement :: Choose -> Choose -- | Get a list of the elements in the complement of a combination. If the -- combination is a subset of k outcomes from n -- possibilities, then the returned list will be sorted and of length -- n-k. complElems :: Choose -> [Int] -- | Return the next combination in lexicographic order, or -- Nothing if there are no further combinations. Starting with -- the first combination and repeatedly calling this function will -- iterate through all combinations of a given order. next :: Choose -> Maybe Choose -- | Return the previous combination in lexicographic order, or -- Nothing if such combination exists. prev :: Choose -> Maybe Choose