combinatorics-0.1.0: Efficient computation of common combinatoric functions.




Binomial coefficients, aka the count of possible combinations. For negative inputs, all functions return 0 (rather than throwing an exception or using Maybe).



choose :: Integral a => a -> a -> aSource

Exact binomial coefficients. For a fast approximation see math-functions:Numeric.SpecFunctions.choose instead. The naive definition of the binomial coefficients is:

 n `choose` k
     | k < 0     = 0
     | k > n     = 0
     | otherwise = factorial n `div` (factorial k * factorial (n-k))

However, we use a fast implementation based on the prime-power factorization of the result (Goetgheluck, 1987). Each time n is larger than the previous calls, there will be some slowdown as the prime numbers must be computed (though it is still much faster than the naive implementation); however, subsequent calls will be extremely fast, since we memoize the list of primes. Do note, however, that this will result in a space leak if you call choose for an extremely large n and then don't need that many primes in the future. Hopefully future versions will correct this issue.