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