import java.util.HashMap;
/**
* Métodos de conveniencia para combinaciones determinísticas.
*
* Uso:
*
* Factorial f = new Factorial();
* long ten_over_two = f.over(10,2); //tarda un poco, ya que no hay caché todavía
* System.out.println( f.factorial( 8)); //instantáneo
*
*
* Notas:
* instanciar y usar, reutilizará su propia caché, por lo que después de un tiempo se supone que se ejecutará en O(1).
* El código es súper rápido (0.0ms)
* Para números muy grandes, use la aproximación de Stirling, @see http://en.wikipedia.org/wiki/Stirling%27s_approximation
* El desbordamiento es un gran problema.
* el valor máximo es 9223372036854775807 < 21!,
* 1.7976931348623157E308 <171!
* Ya sea que sea súper rápido o se rompa, las combinaciones crecen demasiado rápido, y para 2k~n es el mayor;
* ni siquiera puede manejar (29 14) pero para k/n pequeño puede funcionar apenas.
*
*/
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;
}
/**
*
* Este método calcula (n k) = n!/(k! * (n-k)!)
*
* Ejemplo de uso:
* over(52,2) = 2598960
* over(5,2) = 10
* over(2,2) = 1 //ignorando intercambios
*
* @param n el conjunto grande
* @param k cuántos sacar de n
* @return todas las combinaciones de sacar k de n, ignorando intercambios. Simplemente doble la cantidad para tener en cuenta intercambios.
*
*/
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
