n Parts for Sum in PHP

I was bouncing around on Stack Overflow, answering questions here, voting on questions and answers there, when I came across a question on how to construct an array of arbitrary size, whose members add up to an explicit sum. This sounded fun, especially since math has always been an area I’d like to see some personal growth in.

So I set out to answer the question, jotting down some pseudo-code in notepad, and working through some functional portions on writecodeonline.com/php and coderpad.org. After about 10 minutes or so I felt as though I had a good solution for the OP (original poster), so I clicked back over to my Stack Overflow tab. To my terror, the question had been closed as a duplicate.

Now what? Did I just waste all that time and brain-power constructing a solution that I cannot even share? Meh, screw it, I’ll share it on my blog!

My first step was to build up an array of values that were each a fraction of the sum, rounded down to keep away from decimals. This would, of course, leave me with a slightly larger number in the end if the sum isn’t equally divisible by the expected number of parts. That’s okay, I’ll just push that last number onto the end of the array.

$sum = 200; 
$parts = 10; 
$valus = array();

for ( $i = 0; $i < $parts; $i++ ) {
  $num = $i < ( $parts - 1 )
    ? floor( $sum / $parts )
    : $sum - array_sum( $valus );
  array_push( $valus, $num );
}

Awesome. This results in an array of values that are almost entirely the same number, with the exception of the last index, which will be slightly larger when the sum doesn’t divide equally.

Next I need to randomize the values. I figured I would cycle back through and have some of the values share the wealth, so to speak. Each number would have a random portion of itself donated to a random sibling. At the very least, any particular number could be reduced to 1, but no lower (more on that in a bit).

foreach ( $valus as $key => &$value ) {
  if ( $value == 1 ) continue;
  $rVal = rand( 1, $value - 1 );
  $rKey = rand( 1, $parts );
  while ( $rKey == ( $key + 1 ) )
    $rKey = rand( 1, $parts );
  $value -= $rVal;
  $valus[--$rKey] += $rVal;
}

That’s it! (KEEP READING! One important change yet to be made) Tell it how much, and how many, and it builds an array of randomized values for you. One run of the code against the above settings resulted in the following output:

Array
(
  [0] => 26
  [1] => 59
  [2] => 4
  [3] => 61
  [4] => 35
  [5] => 1
  [6] => 2
  [7] => 7
  [8] => 1
  [9] => 4
)

One interesting thing I noticed after toying with the input was that if your sum is less than your number of parts, the code will at times provide a negative number in order to provide adjusted values for each key. For example:

$sum = 2;
$parts = 5;

Produced the following results after one run:

Array
(
  [0] => -1
  [1] => 0
  [2] => -1
  [3] => 3
  [4] => 1
)

Count it up, -1 + 0 + -1 + 3 + 1 indeed equals 2. Of course this wasn’t at all what I wanted. But it did cause me to consider what would happen if somebody wanted more parts than their provided sum. This lead me to return to my share the wealth portion and rewrite the first condition:

if ( $value <= 1 ) continue; // change == to <=

Now, whenever our current value is less than or equal to 1, we skip it. It is possible for the value to be zero already, because we floor the results of the division in earlier code. If the sum is less than our parts, that result will be a fraction, which we promptly round down to 0. This will now prevent the code from further reducing the value from 0 into negative numbers. In cases where our sum is much larger than our parts, we don’t want to borrow so much from one key that we leave another with 0. This is why I skip if the value is already 1 as well.

So asking again for the following:

$sum = 2;
$parts = 5;

Will output the following array (or one similar to it):

Array
(
  [0] => 0
  [1] => 0
  [2] => 1
  [3] => 0
  [4] => 1
)

One thought on “n Parts for Sum in PHP

Comments are closed.