import java.util.HashMap; /** * Convenience methods for deterministic combinations. * * Usage: * * Factorial f = new Factorial(); * long ten_over_two = f.over(10,2); //takes a while, because no cache yet * System.out.println( f.factorial( 8)); //instantaneous *
* * Notes: * instantiate and use, it will reuse its own cache, so after a while it is supposed to run in O(1). * Code is super fast (0.0ms) * For very big numbers, use Stirling's approximation, @see http://en.wikipedia.org/wiki/Stirling%27s_approximation * Overflow is a big problem. * the max value is 9223372036854775807 < 21!, * 1.7976931348623157E308 <171! * Either it is super fast or it breaks, the combinations grow too fast, and for 2k~n it is biggest; * it cannot even handle (29 14) but for k/n small it can function barely. * */ public class Factorial { static private HashMap cache = new HashMap (); public Double factorial(int n) { Integer N = Integer.valueOf( n ); if(cache.containsKey( N) ) return cache.get( N ); if(n<1) { cache.put( N, 0D ); return 0D; } if(n==1) { cache.put( N, 1D ); return 1D; } Double temp = 1D; for (int i = 1; i < n; i++) { temp*=i; cache.put( i, temp ); } Double prev = factorial(n-1); if(prev>Double.MAX_VALUE/n) throw new IllegalArgumentException("factorial("+n+") overflow"); return n*prev; } // 52!/47! = 52*51*50*49*48 so extra(52,47) = 52*(51,47) ... and (47,47)=1 private Double extra(int n, int minus) { if(n<=minus) return 1D; Double result = extra(n-1,minus); if(result>Double.MAX_VALUE/n) throw new IllegalArgumentException( "overflow"); return n* result; } /** * * This method computes (n k) = n!/(k! * (n-k)!) * * Example usage: * over(52,2) = 2598960 * over(5,2) = 10 * over(2,2) = 1 //ignoring swaps * * @param n the big set * @param k how much to draw out of n * @return all combinations of drawing k out of n, ignoring swaps. Simply double the amount for regarding swaps. * */ public Double over(int n, int k){ if(k==n) return 1D; if(k>n) return 0D; if(k<=0) return 0D; //k>=1 and n>k if(k