Skip to content

Instantly share code, notes, and snippets.

Created July 29, 2010 18:25
Show Gist options
  • Save anonymous/498838 to your computer and use it in GitHub Desktop.
Save anonymous/498838 to your computer and use it in GitHub Desktop.
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
public class Test {
private static final int CLUMP = 10;
private static BigInteger[][][] results;;
private static BigInteger foo(int ones, int zeroes, int minTrailing) {
if (ones<CLUMP || zeroes<0) return BigInteger.ZERO;
BigInteger result = results[ones][zeroes][minTrailing];
if (result!=null) return result;
result =
foo(ones-1, zeroes, Math.max(0, minTrailing-1)) // set C
.add(binomialCoefficient(ones+zeroes-CLUMP, zeroes)) // set D
.subtract(foo(ones-1, zeroes, CLUMP-1)) // set E
; // set B
if (minTrailing==0) result = result.add(foo(ones, zeroes-1, 0)); // set A
results[ones][zeroes][minTrailing] = result;
System.out.println("f("+ones+","+zeroes+","+minTrailing+") = "+result);
return result;
}
private static BigInteger binomialCoefficient(int m, int n) {
BigInteger result = BigInteger.ONE;
n = Math.max(n, m-n);
for (int i = m; i>n; i--) result = result.multiply(new BigInteger(Integer.toString(i)));
for (int i = m-n; i>0; i--) result = result.divide(new BigInteger(Integer.toString(i)));
return result;
}
public static void main(String[] args) {
int ones = 128;
int zeroes = 288;
results = new BigInteger[ones+1][zeroes+1][CLUMP];
BigInteger clumpWays = foo(ones, zeroes, 0);
BigInteger ways = binomialCoefficient(ones+zeroes, ones);
System.out.println("With "+ones+" ones and "+zeroes+ " zeroes,");
System.out.println(clumpWays+" ways with clumps of "+CLUMP+" out of ");
System.out.println(ways+" ways");
System.out.println("= "+new BigDecimal(clumpWays).divide(new BigDecimal(ways), MathContext.DECIMAL32)+" chance");
System.out.println("or 1 out of "+new BigDecimal(ways).divide(new BigDecimal(clumpWays), MathContext.DECIMAL32));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment