ڲ      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstu v w x y z { | } ~  3Infinite list of primes, using the TMWE algorithm. KA relatively simple but still quite fast implementation of list of primes.  By Will Ness  Ghttp://www.haskell.org/pipermail/haskell-cafe/2009-November/068441.html @List of primes, using tree merge with wheel. Code by Will Ness. 2Groups integer factors. Example: from [2,2,2,3,3,5] we produce [(2,3),(3,2),(5,1)] $The naive trial division algorithm. Largest integer k such that 2^k is smaller or equal to n Smallest integer k such that 2^k is larger or equal to n TInteger square root (largest integer whose square is smaller or equal to the input)  using Newton'Ns method, with a faster (for large numbers) inital guess based on bit shifts. >Smallest integer whose square is larger or equal to the input +We also return the excess residue; that is   (a,r) = integerSquareRoot' n  means that  a*a + r = n  a*a <= n < (a+1)*(a+1) Newton';s method without an initial guess. For very small numbers (< 10^10) it , is somewhat faster than the above version. Efficient powers modulo m. ! powerMod a k m == (a^k) `mod` m 8Miller-Rabin Primality Test (taken from Haskell wiki). - We test the primality of the first argument n by using the second argument a as a candidate witness.  If it returs False, then n is composite. If it returns True, then n is either prime or composite. A random choice between 2 and (n-2) is a good choice for a.    The series [1,0,0,0,0,...]4, which is the neutral element for the convolution. UConvolution of series. The result is always an infinite list. Warning: This is slow! (Convolution of many series. Still slow! Power series expansion of  1 1 / ( (1-x^k_1) * (1-x^k_2) * ... * (1-x^k_n) )  Example: (coinSeries [2,3,5])!!k is the number of ways  to pay k4 dollars with coins of two, three and five dollars. TODO: better name? CGeneralization of the above to include coefficients: expansion of > 1 / ( (1-a_1*x^k_1) * (1-a_2*x^k_2) * ... * (1-a_n*x^k_n) ) Convolution of many +, that is, the expansion of the reciprocal  of a product of polynomials The same, with coefficients. AThis is the most general function in this module; all the others " are special cases of this one. The power series expansion of / 1 / (1 - x^k_1 - x^k_2 - x^k_3 - ... - x^k_n) "Convolve with (the expansion of) / 1 / (1 - x^k_1 - x^k_2 - x^k_3 - ... - x^k_n) The expansion of ? 1 / (1 - a_1*x^k_1 - a_2*x^k_2 - a_3*x^k_3 - ... - a_n*x^k_n) "Convolve with (the expansion of) ? 1 / (1 - a_1*x^k_1 - a_2*x^k_2 - a_3*x^k_3 - ... - a_n*x^k_n) !""Convolve with (the expansion of)  4 1 / (1 +- x^k_1 +- x^k_2 +- x^k_3 +- ... +- x^k_n) Should be faster than using .  Note:  corresponds to the coefficient -1 in  (since 1 there is a minus sign in the definition there)!  !" !" !" #"Tuples"A fitting into a give shape. The order is lexicographic, that is,  ( sort ts == ts where ts = tuples' shape  Example:  tuples' [2,3] = M [[0,0],[0,1],[0,2],[0,3],[1,0],[1,1],[1,2],[1,3],[2,0],[2,1],[2,2],[2,3]] $ positive "tuples" fitting into a give shape. %# = \prod_i (m_i + 1) &# = \ prod_i m_i 'length (width) maximum (height) (length (width) maximum (height) )# = (m+1) ^ len *# = m ^ len + #$%&'()*+ #$%&'()*+ #$%&'()*+ , (-1)^k- A000142. . A006882. / A007318. 0JA given row of the Pascal triangle; equivalent to a sequence of binomial C numbers, but much more efficient. You can also left-fold over it. - pascalRow n == [ binomial n k | k<-[0..n] ] 12Catalan numbers. OEIS:A000108. 3Catalan's triangle. OEIS:A009766.  Note: " catalanTriangle n n == catalan n G catalanTriangle n k == countStandardYoungTableaux (toPartition [n,k]) 4CRows of (signed) Stirling numbers of the first kind. OEIS:A008275.  Coefficients of the polinomial (x-1)*(x-2)*...*(x-n+1). + This function uses the recursion formula. 5;(Signed) Stirling numbers of the first kind. OEIS:A008275.  This function uses 4, so it shouldn' t be used  to compute many Stirling numbers. 63(Unsigned) Stirling numbers of the first kind. See 5. 73Stirling numbers of the second kind. OEIS:A008277. ) This function uses an explicit formula. 8Bernoulli numbers. bernoulli 1 == -1%2 and bernoulli k == 0 for  k>2 and odd<. This function uses the formula involving Stirling numbers A of the second kind. Numerators: A027641, denominators: A027642. ,-./012345678 ,-./012345678 ,-./012345678 9All possible ways to choose k elements from a list, without  repetitions. "Antisymmetric power" for lists. Synonym for  kSublists. :All possible ways to choose k elements from a list, with repetitions.  "Symmetric power" for lists. See also Math.Combinat.Combinations.  TODO: better name? ;A synonym for :. <" Tensor power" for lists. Special case of =:  4 tuplesFromList k xs == listTensor (replicate k xs)  See also Math.Combinat.Tuples.  TODO: better name? ="Tensor product" for lists. >4Sublists of a list having given number of elements. ?# = binom { n } { k }. @All sublists of a list. A# = 2^n. 9:;<=>?@A 9:;<=>@?A 9:;<=>?@ABCCompositions fitting into a given shape and having a given degree. ) The order is lexicographic, that is, 0 sort cs == cs where cs = compositions' shape k shape sum CD-All compositions fitting into a given shape. E Compositions of a given length. length sum F# = \binom { len+d-1 } { len-1 } G)Positive compositions of a given length. length sum HBCDEFGHBCDEFGHBCDEFGH I-Integer vectors. The indexing starts from 1. J;The additional invariant enforced here is that partitions ; are monotone decreasing sequences of positive integers. K4Sorts the input, and cuts the nonpositive elements. L&Assumes that the input is decreasing. M9Checks whether the input is a partition. See the note at N! N9Note: we only check that the sequence is ordered, but we do not check for N negative elements. This can be useful when working with symmetric functions. % It may also change in the future... OP#The first element of the sequence. QThe length of the sequence. RSThe weight of the partition 5 (that is, the sum of the corresponding sequence). T#The dual (or conjugate) partition. UV Example: # elements (toPartition [5,2,1]) == % [ (1,1), (1,2), (1,3), (1,4), (1,5)  , (2,1), (2,2), (2,3), (2,4)  , (3,1)  ] WXComputes the number of " automorphisms" of a given partition. YZ;Partitions of d, fitting into a given rectangle, as lists. (height,width) d [SPartitions of d, fitting into a given rectangle. The order is again lexicographic. (height,width) d \]Partitions of d, as lists ^Partitions of d. _`/All partitions fitting into a given rectangle. (height,width) a%All partitions up to a given degree. b# = \binom { h+w } { h } cdPartitions of a multiset. e+Vector partitions. Basically a synonym for g. fg!Generates all vector partitions  (" algorithm M" in Knuth). , The order is decreasing lexicographic. IJKLMNOPQRSTUVWXYZ[\]^_`abcdefgJMLKNOPQRSTUVWXY[Z\^]_`abcdIefgIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghAdds unique labels to a . iAdds unique labels to a  jkl>Attaches the depth to each node. The depth of the root is 0. mnop/Attaches the number of children to each node. qrstAComputes the set of equivalence classes of rooted trees (in the % sense that the leaves of a node are  unordered)  with  n = length ks% leaves where the set of heights of / the leaves matches the given set of numbers. ( The height is defined as the number of edges from the leaf to the root. TODO: better name? hijklmnopqrst thijklmnopqrs hijklmnopqrst 'u;Disjoint cycle notation for permutations. Internally it is [[Int]]. vNStandard notation for permutations. Internally it is an array of the integers [1..n]. wxy7Assumes that the input is a permutation of the numbers [1..n]. z{9Checks whether the input is a permutation of the numbers [1..n]. |Checks the input. }Returns n2, where the input is a permutation of the numbers [1..n] ~This is compatible with Maple's  convert(perm,'disjcyc'). Plus 1 or minus 1. 9Action of a permutation on a set. If our permutation is  encoded with the sequence  [p1,p2,...,pn], then in the  two-line notation we have   ( 1 2 3 ... n )  ( p1 p2 p3 ... pn ) .We adopt the convention that permutations act  on the left 5 (as opposed to Knuth, where they act on the right).  Thus,  C permute pi1 (permute pi2 set) == permute (pi1 `multiply` pi2) set 3The second argument should be an array with bounds (1,n). ' The function checks the array bounds. The list should be of length n. *Multiplies two permutations together. See  for our  conventions. The inverse permutation. The trivial permutation. A synonym for  Permutations of [1..n]* in lexicographic order, naive algorithm. # = n! A synonym for . A synonym for . ,Generates a uniformly random permutation of [1..n].  Durstenfeld's algorithm (see  *http://en.wikipedia.org/wiki/Knuth_shuffle). Generates a uniformly random cyclic permutation of [1..n].  Sattolo's algorithm (see  *http://en.wikipedia.org/wiki/Knuth_shuffle). ,Generates all permutations of a multiset. - The order is lexicographic. A synonym for  # = \frac { (sum_i n_i) ! } { \prod_i (n_i !) } *Generates all permutations of a multiset  (based on " algorithm L"& in Knuth; somewhat less efficient). ! The order is lexicographic. $uvwxyz{|}~$vuwxyz{|}~$uvwxyz{|}~  An element (i,j)2 of the resulting tableau (which has shape of the F given partition) means that the vertical part of the hook has length i,  and the horizontal part j. The  hook length is thus i+j-1.  Example: - > mapM_ print $ hooks $ toPartition [5,4,1] ! [(3,5),(2,4),(2,3),(2,2),(1,1)]  [(2,4),(1,3),(1,2),(1,1)]  [(1,1)] *Standard Young tableaux of a given shape. " Adapted from John Stembridge,   ?http://www.math.lsa.umich.edu/~jrs/software/SFexamples/tableaux. hook-length formula ,Semistandard Young tableaux of given shape, "naive" algorithm Stanley'$s hook formula (cf. Fulton page 55)  Set of (i,j) pairs with i>=j>=1. Triangular arrays      Generates all tableaux of size k. Effective for k<=6.   CCombinations fitting into a given shape and having a given degree. ) The order is lexicographic, that is, 0 sort cs == cs where cs = combinations' shape k shape sum -All combinations fitting into a given shape.  Combinations of a given length. length sum # = \binom { len+d-1 } { len-1 } )Positive combinations of a given length. length sum  "8A binary tree with leaves and internal nodes decorated  with types a and b, respectively. .A binary tree with leaves decorated with type a.  Synonym for .  Synonym for .  Synonym for . <Generates all sequences of nested parentheses of length 2n. > Order is lexigraphic (when right parentheses are considered  smaller then left ones).  Based on " Algorithm P") in Knuth, but less efficient because of  the " idiomatic" code. NGenerates a uniformly random sequence of nested parentheses of length 2n.  Based on " Algorithm W" in Knuth. 2Nth sequence of nested parentheses of length 2n.  The order is the same as in .  Based on " Algorithm U" in Knuth. n N; should satisfy 1 <= N <= C(n) *Generates all binary trees with n nodes. $ At the moment just a synonym for . # = Catalan(n) = \frac { 1 } { n+1 } \binom { 2n } { n }. GThis is also the counting function for forests and nested parentheses. >Generates all binary trees with n nodes. The naive algorithm. 1Generates an uniformly random binary tree, using . 'Grows a uniformly random binary tree.  " Algorithm R" (Remy's procudere) in Knuth. J Nodes are decorated with odd numbers, leaves with even numbers (from the  set [0..2n]#). Uses mutable arrays internally. &!!3hijklmnopqrstGenerates graphviz .dot6 file from a forest. The first argument tells whether Q to make the individual trees clustered subgraphs; the second is the name of the  graph. .make the individual trees clustered subgraphs $reverse the direction of the arrows name of the graph Generates graphviz .dot) file from a tree. The first argument is  the name of the graph. #reverse the direction of the arrow name of the graph #$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                \                         !"#$%combinat-0.2.4.1Math.Combinat.Numbers.PrimesMath.Combinat.Numbers.SeriesMath.Combinat.TuplesMath.Combinat.NumbersMath.Combinat.SetsMath.Combinat.CompositionsMath.Combinat.PartitionsMath.Combinat.Trees.NaryMath.Combinat.PermutationsMath.Combinat.TableauxMath.Combinat.Tableaux.KostkaMath.Combinat.CombinationsMath.Combinat.Trees.BinaryMath.Combinat.GraphvizMath.Combinat.HelperMath.Combinat.Trees Math.Combinatprimes primesSimple primesTMWEgroupIntegerFactorsintegerFactorsTrialDivision integerLog2 ceilingLog2isSquareintegerSquareRootceilingSquareRootintegerSquareRoot'integerSquareRootNewton'powerModmillerRabinPrimalityTestSignMinusPlus unitSeriesconvolve convolveMany coinSeries coinSeries'convolveWithCoinSeriesconvolveWithCoinSeries'productPSeriesproductPSeries'convolveWithProductPSeriesconvolveWithProductPSeries'pseriesconvolveWithPSeriespseries'convolveWithPSeries' signValue signedPSeriesconvolveWithSignedPSeriestuples'tuples1' countTuples' countTuples1'tuplestuples1 countTuples countTuples1 binaryTuples paritySign factorialdoubleFactorialbinomial pascalRow multinomialcatalancatalanTrianglesignedStirling1stArraysignedStirling1stunsignedStirling1st stirling2nd bernoullichoosecombinecomposetuplesFromList listTensor kSublistscountKSublistssublists countSublists compositions'countCompositions'allCompositions' compositionscountCompositions compositions1countCompositions1 IntVector Partition mkPartitiontoPartitionUnsafe toPartition isPartition fromPartitionheightwidth heightWidthweight dualPartition_dualPartitionelements _elementscountAutomorphisms_countAutomorphisms _partitions' partitions'countPartitions' _partitions partitionscountPartitionsallPartitions' allPartitionscountAllPartitions'countAllPartitionspartitionMultisetvectorPartitions_vectorPartitionsfasc3B_algorithm_MaddUniqueLabelsTreeaddUniqueLabelsForestaddUniqueLabelsTree_addUniqueLabelsForest_labelDepthTreelabelDepthForestlabelDepthTree_labelDepthForest_labelNChildrenTreelabelNChildrenForestlabelNChildrenTree_labelNChildrenForest_ derivTreesDisjointCycles PermutationfromPermutationpermutationArraytoPermutationUnsafearrayToPermutationUnsafe isPermutation toPermutationpermutationSizefromDisjointCyclesdisjointCyclesUnsafedisjointCyclesToPermutationpermutationToDisjointCyclesisEvenPermutationisOddPermutationsignOfPermutationisCyclicPermutationpermute permuteListmultiplyinverseidentity permutations _permutationspermutationsNaive_permutationsNaivecountPermutationsrandomPermutation_randomPermutationrandomCyclicPermutation_randomCyclicPermutationrandomPermutationDurstenfeldrandomCyclicPermutationSattolopermuteMultisetcountPermuteMultisetfasc2B_algorithm_LTableau_shapeshape dualTableaucontenthooks hookLengthsrowWordrowWordToTableau columnWordcolumnWordToTableaustandardYoungTableauxcountStandardYoungTableauxsemiStandardYoungTableauxcountSemiStandardYoungTableauxTriunTriTriangularArraytriangularArrayUnsafefromTriangularArray kostkaContent_kostkaContentkostkaTableaux_kostkaTableauxcountKostkaTableaux combinations'countCombinations'allCombinations' combinationscountCombinations combinations1countCombinations1Paren RightParen LeftParenBinTree'Leaf'Branch'BinTreeLeafBranchleafforgetNodeDecorationsparenthesesToStringstringToParenthesesforestToNestedParenthesesforestToBinaryTreenestedParenthesesToForestnestedParenthesesToForestUnsafenestedParenthesesToBinaryTree#nestedParenthesesToBinaryTreeUnsafebinaryTreeToNestedParenthesesbinaryTreeToForestnestedParenthesesrandomNestedParenthesesnthNestedParenthesescountNestedParenthesesfasc4A_algorithm_Pfasc4A_algorithm_Wfasc4A_algorithm_U binaryTreescountBinaryTreesbinaryTreesNaiverandomBinaryTreefasc4A_algorithm_RDot binTreeDot binTree'Dot forestDottreeDotdebugswapequatingreverseOrderingreverseCompare groupSortBynubOrdcountfromJust intToBool boolToIntnestunfold1unfold unfoldEitherunfoldM mapAccumMfind2kmpow'mulMod squareModpowModcontainers-0.4.1.0 Data.TreeTreeForest derivTrees'#randomPermutationDurstenfeldSattoloReverseHoleTableauReverseTableauHolebinom2index'deIndex'toHolenextHolereverseTableau normalize normalize' startHole enumHoleshelper newLines'newLinessizes' parenToChar subForest rootLabelNodedigraphBracket binTreeDot' binTree'Dot'