Web Cash

In statistics and probability, the combination is something special. There are tons of problems that revolve around how many combinations you can get choosing a certain number of random items from a set.

We’ve developed mathematical formulas to help us determine the number of possible combinations - and therefore the possibility of getting any single combination - but how can we generate a list of the actual combinations?

Find the Number of Combinations: the Binomial Coefficient

Previously, we looked at how to find the total number of combinations.

Mathematically, we can use the binomial coefficient to figure this out. With a given set size (i.e. 52 cards) and a given sample size (i.e. 7 cards per hand), we can write the equation - (52 Choose 7). We could then re-write the equation as (52! / (7! * 45!) ).

In order to calculate this, we found the most efficient way was to construct two loops. The first loop calculated the numerator - after having canceled out all of the numbers contained in 45!. We then calculated the numerator by looping through 7!. With simple division, we come up with the answer.

Listing the Actual Combinations

A more interesting task, though, is to figure out how to generate a list of these combinations. To do that, let’s take a look at a manually generated list - (6 Choose 3) - and look for a pattern.

Here’s the first few combinations…

123
12 4
12  5
12   6
1 34
1 3 5
1 3  6
1   45
1   4 6
1    56
 234
 23 5

You’ll notice that there’s a pattern and that the combinations seem to be developing sequentially. If we can understand that pattern and write a script to repeat it, we’ll have done our job.

Here’s the gist of the pattern. We look at the last number. If we can increment that, we do. If not, we look back one number. If we can increment, we do. If we increment that number, we “rewind” the next number to be equal to it plus one.

For example, look at this series.

12   6
1 34

We started by incrementing the last number until it maxed out at 6. Then we moved back one space, incremented that number, and set the other number equal to one greater than that. The same thing happens when the last two numbers max out.

1   56
 234

You move back to the number that can be incremented, increment it, and then set the other numbers to one greater than the number incremented.

Using Hard-coded Loops

The easy (and cheating) way to do this is to hard code a series of nested loops that follow this pattern.

The general formula is (k Choose n) - where k is the total number of items in the set and n is the sample size being taken. We will need to create n nested loops - represent each item being chosen in our sample set.

The outer loop will go from 1 to k - (n - 1). Why? Because at k - (n - 1), we can’t increment the outer number anymore. Imagine the real numbers are (6 Choose 3). Once the outer loop gets to 4, we won’t be able to increment it any further - we’ll be at the final combination, 4, 5, 6.

The inner loop will have a beginning value that depends on the outer loop. If the outer loop is in its first iteration, the first inner loop starts at 2. When the outer loop is in its second iteration, the first inner loop starts at 3. It’s always one greater. It’s maximum value is always the same - k - (n - 2) - for the same reason we created the upper limit for the outer loop.

This continues until we get to the inner-most loop.

Here’s what these nested loops might look like in PHP, generating the combinations for (6 Choose 3).

for ($a = 1; $a <= (6 - 2); $a++) {
  for ($b = ($a + 1); $b <= (6 - 1); $b++) {
    for ($c = ($b + 1); $c <= (6 - 0); $c++) {
      echo $a . ' ' . $b . ' ' . $c . "\r\n";
    }
  }
}

You’ll see that that script outputs the correct 20 combinations for (6 Choose 3).

Can We Improve On That?

Surely we can. The main problem here is that we’ve hard-coded the loops. This is ok for a short-term solution and a small number of items being chosen.

What if you had to choose twenty items from a larger set? You’d have to hard-code twenty loops. It makes the code a bit more unseemly. This is also inflexible - you’ll have to change the code every time you have a different problem.

Instead, we need to look for a generalizable solution. This is always the best bet, but sometimes it can be tempting to look for a one-off short term solution because it’s more readily visible.

There is, however, a generalizable solution to this problem. The key lies in creating a function that finds the next combination using the sequential method outlined above. It takes a combination and returns a combination - and you can continuously call the function to iterate through all of the combinations.

Think on that for a while. It’s an interesting challenge. I’ll explain a solution to it later in the week.

Tags: math, php, probability, random