Web Cash

Previously, we looked at how to calculate a binomial coefficient (to find the total number of possible combinations) and an example of how to generate a list of combinations with hard-coded loops.

A function would be much more useful to us if it was flexible - if it could generate a list of combinations for any size set of numbers. We can’t do this with the hard coded loop solution, so we need to come up with a better method.

The Function Concept

Logically, the best way to do this is to create a function that takes a set of numbers (one combination), the size of the set being chosen from (x in [xCy]), and the size of the set being chosen (y in [xCy]). The function would then use a sequential pattern to calculate the next possible combination and return it.

With this type of function, we could create a while loop that iterates through the whole set of possible combinations. We initialize it with the first possible combination, continue to execute while the function returns a combination, and finish when the function returns 0 - in which case there are no more combinations.

If we’re finding the possible combinations for (11 Choose 4), the main loop would look something like this.

$combo = array();
$total = 11;
$choose = 4;
 
while ( $combo = getNextCombo($combo, $total, $choose) ) {
  //  Process the combo here
  //  Store it in a file, an array, or something
  //  Or just out put it
  foreach ($combo as $number) {
    echo $number . ' ';
  }
  echo '<br />';
}

This initializes an empty array - $combo. Our function takes the array and populates it with the next possible combination.

If the array is empty, it’ll create the first combination - {1, 2, 3, 4}. Otherwise, it will increment that set by one to get the next possible combination set - {1, 2, 3, 5}. When the function receives a combination set it can’t possibly increment - {8, 9, 10, 11} - it returns false and the loop ends.

Ok… How Do We Build the Function?

Let’s start by creating the function, checking for an empty array, and returning the initial set. Then we can dive into how we go about incrementing one combination set to get the next one.

function getNextCombo($combo, $total, $choose) {
  if ( empty($combo) ) {
    //  Return the first set, i.e. {1, 2, 3, 4}
    for ($x = 1; $x <= $choose; $x++) {
      $combo[$x] = $x;
    }
 
    return $combo;    
  } else {
    //  Here we'll calculate the next combination
  }
 
  //  If we didn't return before, no combination was found
  return false;
}

That should be pretty self-explanatory. Now we can look at our pattern and develop a method of calculating the next possible combination.

The Pattern

In the last article on getting combinations, we identified the basic pattern to follow.

• Find the “deepest” number that can be incremented
• Increment it by one
• Set any “deeper” numbers to one plus the previous number

The “depeest” number would be the last digit. In the set {1, 2, 3, 4}, the fourth position would be considered deepest. Here’s the first step - and the most basic increment to do.

1 2 3 4
1 2 3 5

The fourth position, ‘4′, is the deepest. It can be incremented. We increment it by one. There are no deeper numbers, so we’re done.

Let’s say the fourth position is maxed out. What happens?

1 2 3 11
1 2 4 5

We move back on position to the third position. This one, ‘3′, is the deepest number that can be incremented. We increment it by one to 4. Then we go down the line and set each number after it to one more than the previous. In this case we only have to set the fourth digit to one more than the third, which is 5.

Let’s take a look at one more example.

1 2 10 11
1 3 4 5

Same thing here. We move back to the second digit to find one we can increment. We increment it. We then drag the others back to be one greater than it.

Writing This in Code

The following code should go in the else { } area of the function above.

The first thing we need to do is find the deepest number that can be incremented. The deepest digit can’t be incremented when it equals $total. The second deepest digit can’t be incremented when it equals ($total - 1). The next one at ($total - 2), then ($total - 3), etc.

This loop puts that pattern into practice.

$moveBack = 0;
  while ( ($combo[$choose - $moveBack] == $total - $moveBack) 
             && ($moveBack < $choose)) {
    $moveBack++;
  }

At the end, $moveBack will hold the number of spaces from the end of the deepest digit. If $moveBack == 0, then the deepest digit can be incremented. If $moveBack == 1, we have to move up one digit to increment. So on and so forth.

If $moveBack == $choose, we can stop counting. That means that no more digits can be incremented - we’ve counted all the way back to digit #0.

Incrementing to the Next Set

Now that we know which digit can be incremented, we can increment the whole set and return the array.

First, we should check if $moveBack == $choose (to see if we’re done). If it doesn’t, we start incrementing.

We start by incrementing $combo[$choose - $moveBack]. Then we loop through, decrementing $moveBack until it is 0 - and we update the deepest digit.

if ($moveBack != $choose) {
  //  Increment the deepest digit that can be incremented
  $combo[$choose - $moveBack]++;
 
  //  Loop through and set all other numbers based on this
  while ($moveBack > 0) {
    $moveBack--;
    $combo[$choose - $moveBack] = $combo[$choose - ($moveBack + 1)] + 1;			
  }
 
  //  $combo now holds the next combination
  return $combo;
} else {
  //  We couldn't increment.  The set passed
  //    to the function was the last possible set.
  return false;	
}

And… We’re Done

If you put all the pieces together correctly, you should now have a function that iterates through all of the possible combinations given a binomial coefficient.

If you were handling large sets (millions of possible combinations), you’d probably want to re-write this in a compiled language. However, the logic is simple and based simply on arrays - so it should be easily portable to any language.

A word of warning about storing the information. Don’t try to store all of the possible combinations in a giant array. It’ll choke up all your RAM and eventually kill the script. I forget how many combinations I tried to calculate that way, but PHP maxed out at 130mb of RAM and died.

Your best bet would be to write the combinations to a data file or a database as you go. This dumps the storage requirements into a more capable format.

So what do you do with this? I’m not really sure. I wrote the script for a guy who was working on a statistical program he was using for his doctoral thesis. I’m sure there are other specialized purposes for the script - statistics and probability.

If nothing else, it’s an interesting look at how to write a computer program to tackle a complex math problem.

Here’s the full source of the script, if you had trouble putting the pieces together.

function getNextCombo($combo, $total, $choose) {
  if ( empty($combo) ) {
    //  Return the first set, i.e. {1, 2, 3, 4}
    for ($x = 1; $x <= $choose; $x++) {
      $combo[$x] = $x;
    }
 
    return $combo;    
  } else {
    $moveBack = 0;
    while ( ($combo[$choose - $moveBack] == $total - $moveBack) 
             && ($moveBack < $choose)) {
      $moveBack++;
    }
  }
  if ($moveBack != $choose) {
    //  Increment the deepest digit that can be incremented
    $combo[$choose - $moveBack]++;
 
    //  Loop through and set all other numbers based on this
    while ($moveBack > 0) {
      $moveBack--;
      $combo[$choose - $moveBack] = $combo[$choose - ($moveBack + 1)] + 1;			
    }
    //  $combo now holds the next combination
    return $combo;
  } else {
    //  We couldn't increment.  The set passed
    //    to the function was the last possible set.
    return false;	
  }
  //  If we didn't return before, no combination was found
  return false;
}
 
$combo = array();
$total = 11;
$choose = 4;
 
while ( $combo = getNextCombo($combo, $total, $choose) ) {
  //  Process the combo here
  //  Store it in a file, an array, or something
  //  Or just out put it
  foreach ($combo as $number) {
    echo $number . ' ';
  }
  echo '<br />';
}

Tags: coding, combinations, math, php, probability, random