001/* 002 * $Id: Combinatoric.java 5596 2016-09-21 21:35:23Z kredel $ 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}