exact-combinatorics- Efficient exact computation of combinatoric functions.

Safe HaskellSafe-Inferred



Binomial coefficients (http://oeis.org/A007318), 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.