h&@K=      !"#$%&'()*+,-./0123456789:;<=>?@ABC D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k  Safe-Inferred^l combinatorialWe only track the number taken by player A because player B will automatically have the complement set.  Safe-Inferredm  Safe-Inferredn combinatorialadd two polynomials or serieso combinatorial"subtract two polynomials or seriesp combinatorial(scale a polynomial or series by a factorq combinatorial"multiply two polynomials or series rsnotpquv Safe-Inferredw combinatorialtreeDepth !! n !! m !! k is the absolute frequency of nodes with depth k in trees with n nodes and depth m. This can't work - the function carries not enough information for recursive definition. treeDepth :: [[[Integer]]] treeDepth = iterate (ls -> zipWith treeDepthIt ([[]]++ls) (ls++[[0]])) [[1]]treeDepthIt :: [Integer] -> [Integer] -> [Integer] treeDepthIt nm0 nm1 = foldl1 add [scale (if null nm0 then 0 else last nm0) (nm0 ++ [1]), scale (sum (init nm1)) nm1, 0 : init nm1]Trees are abstracted to lists of integers, where each integer denotes the number of nodes in the corresponding depth of the tree. The number associated with each tree is the frequency of this kind of tree on random tree generation. combinatorialnodeDepth !! n !! k is the absolute frequency of nodes with depth k in trees with n nodes.  combinatorialnodeDegree !! n !! k? is the number of nodes with outdegree k in a n-node tree.  combinatorialexpected value of node degree   Safe-Inferred snotpqvxyz Safe-Inferred { combinatorialQC.forAll (take 6 <$> QC.arbitrary) $ \xs -> CombPriv.permuteRec xs == CombPriv.permuteMSL (xs::[Int])| combinatorialQC.forAll (genPermuteRep 10) $ \xs -> CombPriv.permuteRep xs == CombPriv.permuteRepM xs} combinatorialQC.forAll genChoose $ \(n,k) -> allEqual $ CombPriv.chooseRec n k : CombPriv.chooseMSL n k : CombPriv.chooseMSL0 n k : []~ combinatorialQC.forAll (QC.choose (-1,7)) $ \n -> QC.forAll genVariate $ \xs -> CombPriv.variateRep n xs == CombPriv.variateRepM n xs combinatorialQC.forAll (QC.choose (-1,7)) $ \n -> QC.forAll genVariate $ \xs -> CombPriv.variateRec n xs == CombPriv.variateMSL n xs combinatorialQC.forAll genTuples $ \(n,xs) -> allEqual $ CombPriv.tuplesRec n xs : CombPriv.tuplesRec0 n xs : CombPriv.tuplesMSL n xs : CombPriv.tuplesMSL0 n xs : [] combinatorialQC.forAll genChooseIndex $ \(n,k,i) -> CombPriv.chooseUnrankRec n k i == CombPriv.chooseUnrankList n k i combinatorialPascal's triangle containing the binomial coefficients. Only efficient if a prefix of all rows is required. It is not efficient for picking particular rows or even particular elements. combinatorialallEqual $ map (take 1000) (CombPriv.derangementNumbersPS0 : CombPriv.derangementNumbersPS1 : CombPriv.derangementNumbersInclExcl : [] :: [[Integer]]) combinatorialequating (take 20) CombPriv.surjectiveMappingNumbersPS (CombPriv.surjectiveMappingNumbersStirling :: [[Integer]]){|}~5 Safe-Inferredn combinatorialPentagonal numbers are used to simplify the infinite product \prod_{i>0} (1-t^i) It is known that the coefficients of the power series are exclusively -1, 0 or 1. The following is a very simple but inefficient implementation, because of many multiplications with zero. combinatorialn.  combinatorial0type Int is needed because of list node indexingQC.forAll (QC.choose (1,10)) $ \k -> QC.forAll (QC.choose (0,50)) $ \n -> Parts.partitionsInc k n == Parts.allPartitionsInc !! k !! nequating (take 30) (map genericLength (Parts.allPartitionsInc !! 1)) Parts.numPartitions     Safe-Inferred Safe-Inferred1' combinatorialGenerate list of all permutations of the input list. The list is sorted lexicographically.Comb.permute "abc"%["abc","acb","bac","bca","cab","cba"]Comb.permute "aabc"["aabc","aacb","abac","abca","acab","acba","aabc","aacb","abac","abca","acab","acba","baac","baca","baac","baca","bcaa","bcaa","caab","caba","caab","caba","cbaa","cbaa"]QC.forAll (take 6 <$> QC.arbitrary :: QC.Gen [Int]) $ \xs -> allEqual $ map (\p -> sort (p xs)) $ Comb.permute : Comb.permuteFast : Comb.permuteShare : [] combinatorialGenerate list of all permutations of the input list. It is not lexicographically sorted. It is slightly faster and consumes less memory than the lexicographical ordering . combinatorialEach element of (allcycles x) has a different element at the front. Iterate cycling on the tail elements of each element list of (allcycles x). combinatorialAll permutations share as much suffixes as possible. The reversed permutations are sorted lexicographically. combinatorial+Comb.permuteRep [('a',2), ('b',1), ('c',1)]["aabc","aacb","abac","abca","acab","acba","baac","baca","bcaa","caab","caba","cbaa"]QC.forAll (genPermuteRep 7) $ \xs -> let perms = Comb.permuteRep $ Key.nub fst xs in perms == nub permsQC.forAll (genPermuteRep 10) $ \xs -> let perms = Comb.permuteRep $ Key.nub fst xs in List.sort perms == Set.toList (Set.fromList perms)QC.forAll (genPermuteRep 10) $ isAscending . Comb.permuteRep . Key.nub fst . sortQC.forAll (QC.choose (0,10)) $ \n k -> Comb.choose n k == Comb.permuteRep [(False, n-k), (True, k)] combinatorial:map (map (\b -> if b then 'x' else '.')) $ Comb.choose 5 3["..xxx",".x.xx",".xx.x",".xxx.","x..xx","x.x.x","x.xx.","xx..x","xx.x.","xxx.."]:map (map (\b -> if b then 'x' else '.')) $ Comb.choose 3 5[]QC.forAll (QC.choose (0,10)) $ \n k -> all (\x -> n == length x && k == length (filter id x)) (Comb.choose n k) combinatorialGenerate all choices of n elements out of the list x with repetitions. "variation" seems to be used historically, but I like it more than "k-permutation".Comb.variateRep 2 "abc".["aa","ab","ac","ba","bb","bc","ca","cb","cc"] combinatorialGenerate all choices of n elements out of the list x without repetitions.Comb.variate 2 "abc"["ab","ac","ba","bc","ca","cb"]Comb.variate 2 "abcd"=["ab","ac","ad","ba","bc","bd","ca","cb","cd","da","db","dc"]Comb.variate 3 "abcd"["abc","abd","acb","acd","adb","adc","bac","bad","bca","bcd","bda","bdc","cab","cad","cba","cbd","cda","cdb","dab","dac","dba","dbc","dca","dcb"]QC.forAll genVariate $ \xs -> Comb.variate (length xs) xs == Comb.permute xs\xs -> equating (take 1000) (Comb.variate (length xs) xs) (Comb.permute (xs::String)) combinatorialGenerate all choices of n elements out of the list x respecting the order in x and without repetitions.Comb.tuples 2 "abc"["ab","ac","bc"]Comb.tuples 2 "abcd"["ab","ac","ad","bc","bd","cd"]Comb.tuples 3 "abcd"["abc","abd","acd","bcd"] combinatorialComb.partitions "abc"[("abc",""),("bc","a"),("ac","b"),("c","ab"),("ab","c"),("b","ac"),("a","bc"),("","abc")]QC.forAll genVariate $ \xs -> length (Comb.partitions xs) == 2 ^ length xs combinatorialNumber of possibilities arising in rectification of a predicate in deductive database theory. Stefan Brass, "Logische Programmierung und deduktive Datenbanken", 2007, page 7-60 This is isomorphic to the partition of n-element sets into k non-empty subsets. http://oeis.org/A048993Comb.rectifications 4 "abc"+["aabc","abac","abbc","abca","abcb","abcc"]map (length . uncurry Comb.rectifications) $ do x<-[0..10]; y<-[0..x]; return (x,[1..y::Int])[1,0,1,0,1,1,0,1,3,1,0,1,7,6,1,0,1,15,25,10,1,0,1,31,90,65,15,1,0,1,63,301,350,140,21,1,0,1,127,966,1701,1050,266,28,1,0,1,255,3025,7770,6951,2646,462,36,1,0,1,511,9330,34105,42525,22827,5880,750,45,1]QC.forAll (QC.choose (0,7)) $ \k xs -> isAscending . Comb.rectifications k . nub . sort $ (xs::String) combinatorialTheir number is k^n. combinatorialAll ways of separating a list of terms into pairs. All partitions are given in a canonical form, sorted lexicographically. The canonical form is: The list of pairs is ordered with respect to the first pair members, and the elements in each pair are ordered. The order is implied by the order in the input list. http://oeis.org/A123023 combinatorial %chooseUnrank n k i == choose n k !! iQC.forAll (QC.choose (0,10)) $ \n k -> map (Comb.chooseUnrank n k) [0 .. Comb.binomial n k - 1] == Comb.choose n kQC.forAll genChooseIndex $ \(n,k,i) -> Comb.chooseRank (Comb.chooseUnrank n k i) == (n, k, i)\bs -> uncurry3 Comb.chooseUnrank (Comb.chooseRank bs :: (Integer, Integer, Integer)) == bs  combinatorial 9https://en.wikipedia.org/wiki/Combinatorial_number_system! combinatorialQC.forAll (take 8 <$> QC.arbitrary) $ \xs -> length (Comb.permute xs) == Comb.factorial (length (xs::String))QC.forAll (take 6 <$> QC.arbitrary) $ \xs -> sum (map sum (Comb.permute xs)) == sum xs * Comb.factorial (length xs)" combinatorial7Pascal's triangle containing the binomial coefficients.QC.forAll (QC.choose (0,12)) $ \n k -> length (Comb.choose n k) == Comb.binomial n kQC.forAll genBinomial $ \(n,k) -> let (q, r) = divMod (Comb.factorial n) (Comb.factorial k * Comb.factorial (n-k)) in r == 0 && Comb.binomial n k == qQC.forAll (take 16 <$> QC.arbitrary) $ \xs k -> length (Comb.tuples k xs) == Comb.binomial (length (xs::String)) k& combinatorialQC.forAll (genPermuteRep 10) $ \xs -> length (Comb.permuteRep xs) == Comb.multinomial (map snd xs)QC.forAll (QC.listOf $ QC.choose (0,300::Integer)) $ \xs -> Comb.multinomial xs == Comb.multinomial (sort xs)' combinatorial1equalFuncList Comb.factorial Comb.factorials 1000( combinatorialPascal's triangle containing the binomial coefficients. Only efficient if a prefix of all rows is required. It is not efficient for picking particular rows or even particular elements./equalFuncList2 Comb.binomial Comb.binomials 100) combinatorialcatalanNumber n* computes the number of binary trees with n nodes.* combinatorialCompute the sequence of Catalan numbers by recurrence identity. It is &catalanNumbers !! n == catalanNumber n9equalFuncList Comb.catalanNumber Comb.catalanNumbers 1000, combinatorial+Number of fix-point-free permutations with n elements. http://oeis.org/A000166equalFuncList Comb.derangementNumber Comb.derangementNumbers 1000- combinatorialNumber of partitions of an n element set into k. non-empty subsets. Known as Stirling numbers  http://oeis.org/A048993.QC.forAll (QC.choose (0,10000)) $ \k -> QC.forAll (take 7 <$> QC.arbitrary) $ \xs -> length (Comb.setPartitions k xs) == (Comb.setPartitionNumbers !! length (xs::String) ++ repeat 0) !! kQC.forAll (QC.choose (0,7)) $ \k xs -> length (Comb.rectifications k xs) == (Comb.setPartitionNumbers !! k ++ repeat 0) !! length (xs::String). combinatorialsurjectiveMappingNumber n k3 computes the number of surjective mappings from a n element set to a k element set. http://oeis.org/A019538/ combinatorialequalFuncList2 Comb.surjectiveMappingNumber Comb.surjectiveMappingNumbers 20 combinatorial=Multiply two Fibonacci matrices, that is matrices of the form /F[n-1] F[n] \ \F[n] F[n+1]/1 combinatorialNumber of possibilities to compose a 2 x n rectangle of n bricks. ! ||| |-- --| ||| |-- --|>equalFuncList Comb.fibonacciNumber Comb.fibonacciNumbers 10000 combinatorial;Create a list of all possible rotations of the input list.  !"#$%&'()*+,-./01  !"#$%&'()*+,-./01 Safe-Inferred32 combinatorialenumerate n xs list all permutations of xs where the first n= elements do not keep their position (i.e. are no fixpoints).(This is a generalization of derangement.(Naive but comprehensible implementation.3 combinatorial http://oeis.org/A047920QC.forAll genPermutationWOFP $ \(k,xs) -> PermWOFP.numbers !! length xs !! k == length (PermWOFP.enumerate k xs)QC.forAll (QC.choose (0,100)) $ \k -> Comb.factorial (toInteger k) == PermWOFP.numbers !! k !! 0QC.forAll (QC.choose (0,100)) $ \k -> Comb.derangementNumber (toInteger k) == PermWOFP.numbers !! k !! k2323 Safe-Inferred4456564 Safe-Inferred8Z7 combinatorialCf.  board-games package.; combinatorial3Given the code and a guess, compute the evaluation.filter ((Mastermind.Eval 2 0 ==) . Mastermind.evaluate "aabbb") $ replicateM 5 ['a'..'c']["aaaaa","aaaac","aaaca","aaacc","aacaa","aacac","aacca","aaccc","acbcc","accbc","acccb","cabcc","cacbc","caccb","ccbbc","ccbcb","cccbb"]> combinatorialnumberDistinct n k b w computes the number of matching codes, given that all codes have distinct symbols. n is the alphabet size, k the width of the code, b+ the number of black evaluation sticks and w' the number of white evaluation sticks.QC.forAll genMastermindDistinct $ \(n,k,b,w) -> let alphabet = take n ['a'..]; code = take k alphabet in Mastermind.numberDistinct n k b w == (genericLength $ filter ((Mastermind.Eval b w ==) . Mastermind.evaluate code) $ Comb.variate k alphabet)? combinatorialQC.forAll genMastermindDistinct $ \(n,k,_b,w) -> Mastermind.numberDistinctWhite n k w == Mastermind.numberDistinct n k 0 w 789:;<=>? 789:;<=>?  Safe-Inferred; combinatorialCandidate for utility-ht:U combinatorialCount the number of card set orderings with adjacent queen and king. We return a triple where the elements count with respect to an additional condition: (card set starts with an ordinary card ' ', start with queen q, start with king k)allEqual [CardPairs.possibilitiesCardsBorderNaive (CardCount 2 3 5), CardPairs.possibilitiesCardsBorderDynamic (CardCount 5 5 5) ! (CardCount 2 3 5), CardPairs.possibilitiesCardsBorder2Dynamic (CardCount 5 5 5) ! (CardCount 2 3 5)]QC.forAll genCardCount $ \cc -> allEqual [CardPairs.possibilitiesCardsBorderNaive cc, CardPairs.possibilitiesCardsBorderDynamic cc ! cc, CardPairs.possibilitiesCardsBorder2Dynamic cc ! cc]_ combinatorial+Allow both Jack and King adjacent to Queen.CDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`aHIJKCDEFGLMXSTUVWYZ[\]^_`aRQNOP  Safe-Inferred=j combinatorialList of Bell numbers computed with the recursive formula given in Wurzel 2004-06, page 136k combinatorialequalFuncList (\k -> round (Bell.bellSeries (fromInteger k) :: Double)) (Bell.bellRec :: [Integer]) 20jkjk !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFFGHIJKLMNOP Q Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w xy z { | } ~        $&7126< *combinatorial-0.1.1-CTOhjYLFNnWGjtdU2sw1rBCombinatorics.MaxNimCombinatorics.TreeDepthCombinatorics.PartitionsCombinatorics.Coin Combinatorics.Combinatorics.Permutation.WithoutSomeFixpointsCombinatorics.PaperStripGameCombinatorics.MastermindCombinatorics.CardPairsCombinatorics.BellNumbersCombinatorics.Utility Polynomial PowerSeriesCombinatorics.PrivatenumberOfPossibilities nodeDepth treeDepth treeDepthSeqnodeDegreeProbnodeDegreeExpectpropInfProdLinearFactorspropPentagonalsDifPpropPentagonalsDifN numPartitionspentagonalPowerSeriespropPentagonalPowerSeries partitionsInc partitionsDecallPartitionsIncvaluesrepresentationNumbersSinglerepresentationNumberspermute permuteFast permuteShare permuteRepchoose variateRepvariatetuples partitionsrectifications setPartitionspairPartitions chooseUnrankchooseUnrankMaybe chooseRank factorialbinomial binomialSeq binomialGenbinomialSeqGen multinomial factorials binomials catalanNumbercatalanNumbersderangementNumberderangementNumberssetPartitionNumberssurjectiveMappingNumbersurjectiveMappingNumbersfibonacciNumberfibonacciNumbers enumeratenumbers treeOfGamesnumbersOfGamesnumbersOfGamesSeriesEvalblackwhiteevaluate evaluateAllformatEvalHistogramnumberDistinctnumberDistinctWhite$fEqEval $fOrdEval $fShowEval CardCount otherCount queenCount kingCountCardOtherQueenKing charFromCardallPossibilitiesallPossibilitiesSmallallPossibilitiesMediumallPossibilitiesSkatadjacentCouplesSmall exampleOutputpossibilitiesCardsNaivepossibilitiesCardsDynamicpossibilitiesCardsBorderNaivepossibilitiesCardsBorderDynamic possibilitiesCardsBorder2DynamicnumberOfAllPossibilitiescardSetSizeSkatnumberOfPossibilitiesSkatprobabilitySkatcardSetSizeRummynumberOfPossibilitiesRummyprobabilityRummycardSetSizeRummyJKnumberOfPossibilitiesRummyJKprobabilityRummyJK $fEqCardCount$fOrdCardCount $fIxCardCount$fShowCardCount$fEqCard $fOrdCard $fEnumCard $fShowCardbellRec bellSeries gameRound scalarProductaddsubscalemulT fromScalarneg progression differentiateTreeFreqonederivativeCoefficients permuteRec chooseRec variateRec tuplesRecchooseUnrankRecderangementNumbersPS0surjectiveMappingNumbersPS replicateM permuteMSL runPermuteRep permuteRepM?: chooseMSL chooseMSL0 variateRepM variateMSL tuplesRec0 tuplesMSL tuplesMSL0chooseUnrankListderangementNumbersPS1derangementNumbersInclExcl surjectiveMappingNumbersStirlingprodLinearFactorspermuteFastStepfiboMul allCyclessample