1m      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijkl  experimental%Patrick Perry <patperry@stanford.edu>mnopqrstuvwxyz{|}~moqrstuvwxyz{|}~moqrstuvwxyz{|}~  experimental%Patrick Perry <patperry@stanford.edu>5A mutable permutation that can be manipulated in the  monad. The  type argument s( is the state variable argument for the  type. %The immutable permutation data type. # Internally, a permutation of size n is stored as an  0-based array of n /s. The permutation represents a reordering of  the integers  0, ..., (n-1)&. The permutation sents the value p[i] to  i. !Get the size of the permutation. (Get a list of the permutation elements.   experimental%Patrick Perry <patperry@stanford.edu> 5A mutable permutation that can be manipulated in the  monad.   experimental%Patrick Perry <patperry@stanford.edu>/IClass 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. 9Create a new permutation initialized to be the identity. 5Allocate a new permutation but do not initialize it. FGet a lazy list of the permutation elements. The laziness makes this C function slightly dangerous if you are modifying the permutation. =Set all the values of a permutation from a list of elements. 3Construct 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. .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. 8Construct 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. 0Construct a new permutation by copying another. copyPermute dst src( copies the elements of the permutation src  into the permutation dst+. The two permutations must have the same  size. #Set a permutation to the identity.  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 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. swapElems p i j exchanges the ith and jth elements of the  permutation p. FReturns 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]. (Compute the inverse of a permutation. 4Set 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. HAdvance a permutation to the next permutation in lexicogrphic order and  return True4. If no further permutaitons are available, return False and L leave the permutation unmodified. Starting with the idendity permutation  and repeatedly calling setNext- will iterate through all permutations of a  given size. !FStep backwards to the previous permutation in lexicographic order and  return True/. If there is no previous permutation, return False and # leave the permutation unmodified. "EGet 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 C function slightly dangerous if you are modifying the permutation. #EGet a lazy list of swaps equivalent to the inverse of a permutation. $getCycleFrom p i* gets the list of elements reachable from i  by repeated application of p. % getCycles p' returns the list of disjoin cycles in p. &DWhether or not the permutation is made from an even number of swaps ' getPeriod p - The first power of p" that is the identity permutation (3Convert a mutable permutation to an immutable one. )3Convert an immutable permutation to a mutable one. * 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 +. +, getOrder n xs2 returns a permutation which rearranges the first n  elements of xs4 into ascending order. The results are undefined if n is  greater than the length of xs. This is a special case of -. -. getRank n xs< eturns a permutation, the inverse of which rearranges the  first n elements of xs2 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 /. /*  !"#$%&'()*+,-./* &' !"#$%*+,-./()*    !"#$%&'()*+,-./ experimental%Patrick Perry <patperry@stanford.edu>0KA safe way to create and work with a mutable permutation before returning G an immutable one for later perusal. This function avoids copying the N permutation before returning it - it uses unsafeFreeze internally, but this 0 wrapper is a safe interface to that function. ,  !"#$%&'()*+,-./000 experimental%Patrick Perry <patperry@stanford.edu>+  !"#$%&'()*+,-./ experimental%Patrick Perry <patperry@stanford.edu>15Construct an identity permutation of the given size. 23Construct 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. 3.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. 48Construct 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. 5at 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. 6!Get the inverse of a permutation 77Return the next permutation in lexicographic order, or Nothing if L there are no further permutations. Starting with the identity permutation L and repeatedly calling this function will iterate through all permutations  of a given order. 8;Return the previous permutation in lexicographic order, or Nothing  if no such permutation exists. 9@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. :>Get a list of swaps equivalent to the inverse of permutation. ; cycleFrom p i* gets the list of elements reachable from i by  repeated application of p. <cycles p' returns the list of disjoin cycles in p. =DWhether or not the permutation is made from an even number of swaps >period p - The first power of p" that is the identity permutation ? 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 @. @A order n xs2 returns a permutation which rearranges the first n  elements of xs4 into ascending order. The results are undefined if n is  greater than the length of xs. This is a special case of B. BC rank n xs< eturns a permutation, the inverse of which rearranges the  first n elements of xs2 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 D. D123456789:;<=>?@ABCD12345=>6789:;<?@ABCD123456789:;<=>?@ABCD  experimental%Patrick Perry <patperry@stanford.edu>E5A mutable combination that can be manipulated in the  monad. The  type argument s( is the state variable argument for the  type. F<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. GHGet the number of outcomes, k. I!Get the number of possibilities, n. JGet a list of the k outcomes. EFGHIJEFGHIJ  experimental%Patrick Perry <patperry@stanford.edu>K5A mutable combination that can be manipulated in the  monad. KK experimental%Patrick Perry <patperry@stanford.edu>LIClass for representing a mutable combination. The type is parameterized  over the type of the monad, m+, in which the mutable combination will be  manipulated. M!Get the number of possibilities, n in the combination. NGet the number of outcomes, k in the combination. O newChoose n k creates a new combination of k outcomes from n ( possibilites initialized to the subset { 0, ..., k-1 }. P newChoose n k allocates a new combination of k outcomes from  n+ possibilities but does not initialize it. QRSFGet a lazy list of the combination elements. The laziness makes this C function slightly dangerous if you are modifying the combination. T=Set all the values of a combination from a list of elements. UVW3Construct 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. 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. XY0Construct a new combination by copying another. ZcopyChoose dst src( copies the elements of the combination src  into the combination dst+. The two combinations must have the same  size. [6Set a combination to be the first subset of its size. \ 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. ] 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. ^FReturns whether or not the combination is valid. For it to be valid, I 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. _(Compute the complement of a combination `GReturn 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 0 the returned list will be sorted and of length n-k. L Due to the laziness, you should be careful when using this function if you % are also modifying the combination. aCAdvance a combination to the next in lexicogrphic order and return True. 3 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. bFStep backwards to the previous combination in lexicographic order and  return True/. If there is no previous combination, return False and # leave the combination unmodified. c3Convert a mutable combination to an immutable one. d3Convert an immutable combination to a mutable one. LMNOPQRSTUVWXYZ[\]^_`abcdLMNOPQRSTUVWYZ[\]^_`abcdXL MNOPQRSTUVMNOPQRSTUVWXYZ[\]^_`abcd experimental%Patrick Perry <patperry@stanford.edu>eKA safe way to create and work with a mutable combination before returning G an immutable one for later perusal. This function avoids copying the N combination before returning it - it uses unsafeFreeze internally, but this 0 wrapper is a safe interface to that function. ELMNOPQRSTUVWXYZ[\]^_`abcdeEee experimental%Patrick Perry <patperry@stanford.edu>KLMNOPQRSTUVWXYZ[\]^_`abcdK experimental%Patrick Perry <patperry@stanford.edu>f choose n k" returns the first combination of k outcomes from n ! possibilites, namely the subset { 0, ..., k-1 }. g3Construct 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. 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. hat 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. i!Get the inverse of a combination j?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 0 the returned list will be sorted and of length n-k. k7Return the next combination in lexicographic order, or Nothing if I there are no further combinations. Starting with the first combination L and repeatedly calling this function will iterate through all combinations  of a given order. l;Return the previous combination in lexicographic order, or Nothing  if such combination exists. FGHIJfghijkl FfghGIHJijklfghijkl       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR S T   U  VWXYZ[\]^_()+`a./67bcdCefEF g g h h i   j k l m n o p q r  stu vwx  y z { | } ~  vw   S T V permutation-0.4Data.Permute.ST Data.PermuteData.Permute.IOData.Permute.MPermuteData.Choose.ST Data.ChooseData.Choose.IOData.Choose.MChoose Data.IntArrayData.Permute.BaseData.Permute.IOBaseData.Choose.BaseData.Choose.IOBase STPermutePermuteunsafeAtsizeelems IOPermuteMPermutegetSize newPermute newPermute_ unsafeGetElem unsafeSetElemunsafeSwapElemsgetElemssetElems unsafeFreeze unsafeThawnewListPermuteunsafeNewListPermutenewSwapsPermuteunsafeNewSwapsPermutenewCyclesPermuteunsafeNewCyclesPermutenewCopyPermute copyPermute setIdentitygetElemsetElem swapElemsisValid getInverse copyInversesetNextsetPrevgetSwaps getInvSwaps getCycleFrom getCycles getIsEven getPeriodfreezethawgetSort getSortBygetOrder getOrderBygetRank getRankBy runSTPermutepermute listPermute swapsPermute cyclesPermuteatinversenextprevswapsinvSwaps cycleFromcyclesisEvenperiodsortsortByorderorderByrankrankBySTChooseChoosepossibleIOChooseMChoose getPossible newChoose newChoose_ newListChooseunsafeNewListChoose newCopyChoose copyChoosesetFirst getComplement getComplElems runSTChoosechoose listChoose complement complElems STIntArrayIntArray numElements newArray_sameSTIntArraynumElementsSTIntArraygetNumElements unsafeRead unsafeWrite unsafeSwap readElems writeElemsbaseGHC.STSTghc-prim GHC.TypesIntgetSizeSTPermute sizeSTPermute newSTPermute newSTPermute_unsafeGetElemSTPermuteunsafeSetElemSTPermuteunsafeSwapElemsSTPermutegetElemsSTPermutesetElemsSTPermuteunsafeFreezeSTPermuteunsafeThawSTPermuteIO newIOPermute newIOPermute_getSizeIOPermute sizeIOPermuteunsafeGetElemIOPermuteunsafeSetElemIOPermuteunsafeSwapElemsIOPermutegetElemsIOPermutesetElemsIOPermuteunsafeFreezeIOPermuteunsafeThawIOPermuteunsafeInterleaveMnewSwapsPermuteHelp cycleToSwaps setNextBy getSwapsHelp nextPrevHelpgetSizeSTChoose sizeSTChoosegetPossibleSTChoosepossibleSTChoose newSTChoose newSTChoose_unsafeGetElemSTChooseunsafeSetElemSTChoosegetElemsSTChoosesetElemsSTChooseunsafeFreezeSTChooseunsafeThawSTChoose newIOChoose newIOChoose_getPossibleIOChoosepossibleIOChoosegetSizeIOChoose sizeIOChooseunsafeGetElemIOChooseunsafeSetElemIOChoosegetElemsIOChoosesetElemsIOChooseunsafeFreezeIOChooseunsafeThawIOChoose