001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008/**
009 * Combinatoric algorithms. Similar to ALDES/SAC2 SACCOMB module.
010 * @author Heinz Kredel
011 */
012public class Combinatoric {
013
014
015    /**
016     * Integer binomial coefficient induction. n and k are integers with 0
017     * less than or equal to k less than or equal to n. A is the binomial
018     * coefficient n over k. B is the binomial coefficient n over k+1.
019     * @param A previous induction result.
020     * @param n long.
021     * @param k long.
022     * @return the binomial coefficient n over k+1.
023     */
024    public static BigInteger binCoeffInduction(BigInteger A, long n, long k) {
025        BigInteger kp, np;
026        np = new BigInteger(n - k);
027        kp = new BigInteger(k + 1);
028        BigInteger B = A.multiply(np).divide(kp);
029        return B;
030    }
031
032
033    /**
034     * Integer binomial coefficient. n and k are integers with 0 less than
035     * or equal to k less than or equal to n. A is the binomial coefficient n
036     * over k.
037     * @param n long.
038     * @param k long.
039     * @return the binomial coefficient n over k+1.
040     */
041    public static BigInteger binCoeff(int n, int k) {
042        BigInteger A = BigInteger.ONE;
043        int kp = (k < n - k ? k : n - k);
044        for (int j = 0; j < kp; j++) {
045            A = binCoeffInduction(A, n, j);
046        }
047        return A;
048    }
049
050
051    /**
052     * Integer binomial coefficient partial sum. n and k are integers, 0 le k le
053     * n. A is the sum on i, from 0 to k, of the binomial coefficient n over i.
054     * @param n long.
055     * @param k long.
056     * @return the binomial coefficient partial sum n over i.
057     */
058    public static BigInteger binCoeffSum(int n, int k) {
059        BigInteger B, S;
060        S = BigInteger.ONE;
061        B = BigInteger.ONE;
062        for (int j = 0; j < k; j++) {
063            B = binCoeffInduction(B, n, j);
064            S = S.sum(B);
065        }
066        return S;
067    }
068
069
070    /**
071     * Factorial.
072     * @param n integer.
073     * @return n!, with 0! = 1.
074     */
075    public static BigInteger factorial(long n) {
076        if (n <= 1) {
077            return BigInteger.ONE;
078        }
079        BigInteger f = BigInteger.ONE;
080        if (n >= Integer.MAX_VALUE) {
081            throw new UnsupportedOperationException(n + " >= Integer.MAX_VALUE = " + Integer.MAX_VALUE);
082        }
083        for (int i = 2; i <= n; i++) {
084            f = f.multiply(new BigInteger(i));
085        }
086        return f;
087    }
088
089}