Web Cash

I came across this problem on the DigitalPoint forums the other day. How can we write a script to calculate the total number of random combinations in a set (i.e. the binomial coefficient), and how can we generate a list of these combinations?

Today, we’ll tackle the first part. We’ll start with a quick primer on math – what is a binomial coefficient? Then, we’ll look into the most efficient way to calculate that and get the total number of possible combinations.

What Is a Binomial Coefficient?

If it’s been a while since you took statistics or calculus, you might be scratching your head thinking about what a binomial coefficient is and what it has to do with combinations.

If you’re looking at a set of random items – let’s say 52 playing cards – and you want to pick out a number of them – let’s say a 7 card poker hand – the binomial coefficient tells you how many possible combinations you can make.

The general formula for that is usually written:

(x Choose y) = (x!) / (y! * (x-y)!)

In our example above, the total number of combinations you can get in a 7-card poker game is (52! / (7! * 45!)) or somewhere around 130,000,000.

How Do We Calculate That (in PHP)?

These methods of calculation will work for any language, really. We’ll just use PHP as an example.

The simplest way to calculate the binomial coefficient would be to loop through, calculate each factorial, and then evaluate the equation. Notice I said simple, not efficient.

$x = 52;
$y = 7;
 
$num = 1;  //  This is the numerator, 52!
for ($a = 1; $a <= $x; $a++) {
  $num *= $a;
}
 
$denOne = 1;  //  This is the first part of the denominator, 7!
for ($b = 1; $b <= $y; $b++) {
  $denOne *= $b;
}
 
$denTwo = 1;  //  This is the second part of the denominator, 45!
for ($c = 1; $c <= ($x - $y); $c++) {
  $denTwo *= $c;
}
 
$combinations = ($num) / ($denOne * $denTwo);

PHP will evaluate this properly because it’s nice and flexible with data types. Do you know how large 52! is? Try 8.06581751709E+67 large.

This is clearly too big to be an integer value, but PHP quietly converts the values to floats and keeps running. There should be a better way – one where we don’t have to calculate all of the factorials.

Method Two – Using array_diff

This method is a bit more along the lines of human logic. However, it’s still not going to be efficient. Although it’ll work with smaller numbers than the first method, it’ll take more time and memory to compute.

Basically, we’ll create three arrays. One for each set – {1, 2, 3, … 52}, {1, 2, 3, … 7}, {1, 2, 3, … 45}.

Since we know that the third set (45!) will be in the denominator and the first set (52!) will be in the numerator, we can use a nifty function called array_diff to cancel out all of the common values and shrink the numerator for us.

$newNumerator = array_diff($oldNumerator, $oldDenominator);

Then we can calculate the factorials by multiplying all of the values in the array. We can also make use of another PHP function here – array_product. It does more or less what it sounds like – it finds the product of all the values in an array.

$num = array();
for ($a = 1; $a <= $x; $a++) {
  $num[] = $a;  // the numerator array, 52!
}
 
$denOne = array();
for ($b = 1; $b <= $y; $b++) {
  $denOne[] = $b;  //  The first denominator array, 7!
}
 
$denTwo = array();
for ($c = 1; $c <= ($x - $y); $c++) {
  $denTwo[] = $c;  // The second denominator array, 45!
}
 
//  Use array_diff to cancel out the common values in 52! and 45!
$num = array_diff($num, $denTwo);
$combinations = array_product($num) / array_product($denOne);

This keeps the numbers much smaller. Therefore we can work with bigger combinations before PHP putts out. However, the arrays can eat up a lot of memory and processing power… so there still should be a better way.

Combine the Two Concepts

The more efficient way is to combine the two concepts. We’ll use the first method of multiplying through a loop to generate the factorials. This is far more efficient than iterating an array.

However, we’ll still cancel out the common values between 52! and 45!. To do this, we modify the first loop so that it counts down from $x (52) to $x – $y (45). Then we simply ignore the third loop – since it’s values were essentially counted when we calculated the first loop.

$num = 1;
for ($a = $x; $a > $x - $y; $a--) {
  $num *= $a;
}
 
$den = 1;
for ($b = 1; $b <= $y; $b++) {
  $den *= $b;
}
 
$combinations = $num / $den;

At this point, our script is pretty efficient. It doesn’t use up a lot of memory, it executes quickly, and it’s not calculating very many redundant values.

However, there’s still a limit to what we can do. The biggest number PHP seems to be able to calculate is 170!. After PHP sees the value 7.25741561531E+306 it just seems to give up. Geez, like 300 zeroes is a lot.

You could improve this a bit more, and increase the number of combinations it could compute. Rather than calculating the $numerator and $denominator separate, as we did here, you’d want to calculate the $denominator first and then cancel out values as you multiply the numerator.

In other words, calculate the $denominator as normal. Then, while you’re looping through to calculate the numerator, you factor out any common values in the $denominator and the number about to be multiplied into the numerator.

Who Cares About How Many Combinations… I Want to See Them

This is really the boring part. Who cares how many combinations there are? We can easily find that with a calculator.

The interesting part – where we definitely need a computer to help us – is to iterate through the set and find all of the possible combinations. We’ll come back to this later in the week.

Tags: Game Design, math, php, probability, random