# Creating number groups of equal sums

Let’s say I have a randomly generated array of numbers, each valued 1 - 10, that all sum up to 100.

I want to split the numbers in this array into 4 groups, making the sum of the numbers in each group as equal as possible.

Basically the end result would have each group summing up to approximately 25.

I have been brainstorming, but I think I need a little help. Does anyone know I could accomplish doing this in PHP?

sort them and just take every fourth number, alternating on groups of 4, so you would have 4 arrays:
1 => arr[0], arr[7], arr[8], arr[15]…
2 => arr[1], arr[6], arr[9], arr[14]…
3 => arr[2], arr[5], arr[10], arr[13]…
4 => arr[3], arr[4], arr[11], arr[12]…

That is very interesting, but yeah, I suppose it does make sense.

I tried your method with a few examples on paper… and it seems to work pretty well so far, even with unequal amounts of numbers in the groups.

Thank you very much. =)

How does one randomly generate an array of numbers that sum to 100? rand(remainder) until you get to remainder = 0?

Anyway… the method proposed works… fairly well, until of course one of the numbers excedes 25.

Array(85,1,1,1,1,1,1,1,1,1,1,1,1…);
That would make one of the stacks weigh 87, and the others weigh 4 (Roughly). That’s not very even. (The most even output in that event would only be 85,5,5,5 , but it’s an extreme case…

try it with 50,1,1,1,1,1,1,1… most even outcome: 50,17,17,16. The function however would return 63,13,12,12

Try this instead: For each number in sequence: Find smallest Stack. Add number to stack.

The numbers in this case are only 1 - 10. But even in a case with one super-high number, the method still seems efficient.

I mean… that high number has to go in one of the four groups, right? How else would you do it?

Ah you’re right…Though 10,1,1… still results in an imbalance that could be eliminated.

See my post above again. Add the number to the smallest stack, rinse, repeat. (And by ‘smallest’ i mean Sum-Smallest, not Array-Size smallest)

In most cases the results would probably be the same, or close to it. But you do have a valid point. In a situation like that, blindly adding more to an already over-sized group wouldn’t be the most wise.

I’m bored :S

``````
<?php
\$nums = array();
// gen array nume == 100
while(array_sum(\$nums) < 100)
{
if((\$rem = 100 - array_sum(\$nums)) <= 10)
{
array_push(\$nums, \$rem);
break;
}
array_push(\$nums, rand(1,10));
}
sort(\$nums);

// messy, but whatever :|
\$odd = true;
\$new = array(array(), array(), array(), array());
// grab values into 4 arrays
while(!empty(\$nums)) {
for(\$i=0; \$i<4; \$i++)
{
if(\$odd)
{
array_push(\$new[\$i], array_shift(\$nums));
}
else
{
array_push(\$new[3-\$i], array_shift(\$nums));
}
}
}

foreach(\$new as \$v)
{
var_dump(array_sum(\$v));
}

// three refreshes
/*
int(22)
int(24)
int(27)
int(27)

int(25)
int(26)
int(28)
int(21)

int(26)
int(28)
int(21)
int(25)
*/

``````

lol

I did the same thing…
My Results for 100 Tests

``````
<?php
function test() {
\$remainder = 100;
while(\$remainder > 0) {
\$max = (\$remainder > 10) ? 10 : \$remainder;
\$val[] = rand(1,\$max);
\$remainder -= \$val[(count(\$val)-1)];
}

//Method 1
sort(\$val);
\$m1 = array(array(),array(),array(),array());
\$token = 0;
for(\$i = 0; \$i < ceil(count(\$val)/2); \$i++) {
\$m1[\$token][] = \$val[\$i];
if((count(\$val)-(\$i+1)) != \$i) {
\$m1[\$token][] = \$val[(count(\$val)-(\$i+1))];
}
\$token = (\$token + 1) &#37; 4;
}

//Method 2
\$m2 = array(array(),array(),array(),array());
foreach (\$val AS \$num) {
//Find smallest
\$target = 0;
for(\$i = 1; \$i < 4; \$i++) {
if(array_sum(\$m2[\$i]) < array_sum(\$m2[\$target])) {
\$target = \$i;
}
}
\$m2[\$target][] = \$num;
}

//Output
echo "<tr><td>".implode(",",array_map("array_sum",\$m1))."</td><td>".implode(",",array_map("array_sum",\$m2))."</td></tr>";
}

echo "<table border='2' cellpadding='3' cellspacing='10'><tr><th>Method 1</th><th>Method 2</th></tr>";
for (\$i = 0; \$i < 100; \$i++) {
test();
}
echo "</table>";
?>
``````

lol. wow… Well I guess it can’t ever hurt to practice your php skills.

Just for S&G i modified my code to calculate the average difference between the method output and 25,25,25,25, and ran it over 1000 tests instead of 100.

Thus far, Method 1 seems to have an average Diff of ~14… and Method 2 has an average Diff of ~10… so i -think- (if i’m doing my math correctly) that Method 2 is very slightly more accurate at balancing the sums?

hash: Why do you have \$odd = true, but never actually determine if the stack of numbers is odd or not?

That was to flip the array to get 1st, 8th, 9th rather than 1st, 5th, 9th, but looks like I forgot to type \$odd = !\$odd

Ah. Makes sense now.