-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Efficient computation of common combinatoric functions.
--   
--   Efficient computation of common combinatoric functions.
@package combinatorics
@version 0.1.0


-- | The factorial numbers (<a>http://oeis.org/A000142</a>). For negative
--   inputs, all functions return 0 (rather than throwing an exception or
--   using <a>Maybe</a>).
--   
--   Notable limits:
--   
--   <ul>
--   <li>12! is the largest factorial that can fit into <a>Int32</a>.</li>
--   <li>20! is the largest factorial that can fit into <a>Int64</a>.</li>
--   <li>170! is the largest factorial that can fit into 64-bit
--   <a>Double</a>.</li>
--   </ul>
module Math.Combinatorics.Factorial

-- | Exact factorial numbers. For a fast approximation see
--   <tt>math-functions:Numeric.SpecFunctions.factorial</tt> instead. The
--   naive definition of the factorial numbers is:
--   
--   <pre>
--   factorial n
--       | n &lt; 0     = 0
--       | otherwise = product [1..n]
--   </pre>
--   
--   However, we use a fast algorithm based on the split-recursive form:
--   
--   <pre>
--   factorial n =
--       2^(n - popCount n) * product [(q k)^k | forall k, k &gt;= 1]
--       where
--       q k = product [j | forall j, n*2^(-k) &lt; j &lt;= n*2^(-k+1), odd j]
--   </pre>
factorial :: (Integral a, Bits a) => Int -> a


-- | The prime numbers (<a>http://oeis.org/A000040</a>).
module Math.Combinatorics.Primes

-- | The prime numbers. Implemented with the algorithm in:
--   
--   <ul>
--   <li>Colin Runciman (1997) <i>Lazy Wheel Sieves and Spirals of
--   Primes</i>, Functional Pearl, Journal of Functional Programming, 7(2).
--   pp.219--225. ISSN 0956-7968
--   <a>http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096</a></li>
--   </ul>
primes :: [Int]


-- | Binomial coefficients, aka the count of possible combinations. For
--   negative inputs, all functions return 0 (rather than throwing an
--   exception or using <a>Maybe</a>).
module Math.Combinatorics.Binomial

-- | Exact binomial coefficients. For a fast approximation see
--   <tt>math-functions:Numeric.SpecFunctions.choose</tt> instead. The
--   naive definition of the binomial coefficients is:
--   
--   <pre>
--   n `choose` k
--       | k &lt; 0     = 0
--       | k &gt; n     = 0
--       | otherwise = factorial n `div` (factorial k * factorial (n-k))
--   </pre>
--   
--   However, we use a fast implementation based on the prime-power
--   factorization of the result (Goetgheluck, 1987). Each time <tt>n</tt>
--   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 <a>primes</a>. Do note, however,
--   that this will result in a space leak if you call <tt>choose</tt> for
--   an extremely large <tt>n</tt> and then don't need that many primes in
--   the future. Hopefully future versions will correct this issue.
--   
--   <ul>
--   <li>P. Goetgheluck (1987) <i>Computing Binomial Coefficients</i>,
--   American Mathematical Monthly, 94(4). pp.360--365.
--   <a>http://www.jstor.org/stable/2323099</a>,
--   <a>http://dl.acm.org/citation.cfm?id=26272</a></li>
--   </ul>
choose :: Integral a => a -> a -> a