I recently started learning PHP, a language I had never caught up to but that recently became a requirement of my job.

For a start project, just to give myself something meaningful to write in it, I am writing some logic that places items into bins - some examples might include calculating all the ways you could pack N items into M boxes, to try and find the most optimum use of space in your limited set of boxes.

As part of this work, I need a way to figure out all the ways you could divide up those N items between the boxes. For example, if you have 5 things and 2 boxes, you could put all 5 in one, 4 in one and 1 in the other, etc.

In searching around I found the concept of partitions of an integer, which is all the ways you can sum that integer from other positive integers. Just what I was looking for!

But, in looking for an already-written version of this algorithm in PHP, I came up short. Maybe there are some, but I didn’t turn them up in some light searching.

I did find an implementation in Perl though, which looks nice and small and easy.

Being a complete n00b at PHP, and not having written Perl in years, the translation took me a few hours, but it is pretty straightforward:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function nextpart ($part) {
   //collect all the trailing 1s
   $x = 0;
   while (is_array($part) and $part[count($part)-1] == 1) {
      $x += $part[count($part)-1]; //add the last element to x
      array_splice($part,count($part)-1); //remove the last element
   }

   if (!is_array($part) or count($part) == 0) {
      return; //returns null once the array is all ones (and our actions above empties it)
   }
   $part[count($part)-1]--; //take one away from the last element
   $x++; //add it to x
   //re-distribute the collected amount in increments of the value of the last element
   while ($x > $part[count($part)-1]) {
      $part[] = $part[count($part)-1];
      $x -= $part[count($part)-1];
   }
   $part[] = $x;
   return $part;
}

Same caveat as the Perl implementation - there is no error handling here. Also, I am sure I am overdoing the two checks that insure the array is not empty or null - I am still getting use to PHP’s undef, null, and checks (for example, the difference between == and ===). So I am sure some of you PHP gurus could make this shorter and cleaner using better syntax. It works though, with example usage like:

1
2
3
4
5

$partitions = array(5);

do {
   $all_partitions[] = $partitions;
} while ($partitions = nextpart($partitions));

Hope you find this useful.