3 
array
1703 => float 15916.19738
5129 => float 11799.15419
33 => float 11173.49945
1914 => float 8439.45987
2291 => float 6284.22271
5134 => float 5963.14065
5509 => float 5169.85755
4355 => float 5153.80867
2078 => float 3932.79341
31 => float 3924.09928
5433 => float 2718.7711
3172 => float 2146.1932
1896 => float 2141.36021
759 => float 1453.5501
2045 => float 1320.74681
5873 => float 1222.7448
2044 => float 1194.4903
6479 => float 1074.1714
5299 => float 950.872
3315 => float 878.06602
6193 => float 847.3372
1874 => float 813.816
1482 => float 330.6422
6395 => float 312.1545
6265 => float 165.9224
6311 => float 122.8785
6288 => float 26.5426

I would like to distribute this array into two arrays both ending up with a grand total (from the float values) to be about the same.

I tried K-Clustering, but that distributes higher values onto one array and lower values onto the other array. I'm pretty much trying to create baseball teams with even player skills.

Improve this question
2
  • Do you need to distribute the number of players evenly? Or is it fine to put a single player with skill 15 in one array, and fifteen players of skill 1 in another array? Will any player have negative ability? Commented May 24, 2011 at 2:10
  • No negative ability and the K-Clustering did the 1 player with a skill of 15 then 15 with a skill of 1. I'm looking to evenly distribute by the values not really the total sum (in the example you gave me that would pretty much be the answer but not for the real example that I have up there... hope this makes sense). Commented May 24, 2011 at 2:19

3 Answers 3

Reset to default
2

Step 1: Split the players into two teams. It doesn't really matter how you do this, but you could do every other one.

Step 2: Randomly switch two players only if it makes the teams more even.

Step 3: Repeat step 2 until it converges to equality.

  $diff = array_sum($teams[0]) - array_sum($teams[1]);
  for ($i = 0; $i < 1000 && $diff != 0; ++$i)
  {
    $r1 = rand(0, 8); // assumes nine players on each team
    $r2 = rand(0, 8);

    $new_diff = $diff - ($teams[0][$r1] - $teams[1][$r2]) * 2;

    if (abs($new_diff) < abs($diff))
    {
      // if the switch makes the teams more equal, then swap
      $tmp = $teams[0][$r1];
      $teams[0][$r1] = $teams[1][$r2];
      $teams[1][$r2] = $tmp;

      var_dump(abs($new_diff));

      $diff = $new_diff;
    }
  }

You'll have to adapt that code to your own structures, but it should be simple.

Here's a sample output:

int(20)
int(4)
int(0)

I was using integers from 0 to 100 to rate each player. Notice how it gradually converges to equality, although an end result of 0 is not guaranteed.

You can stop the process after a fixed interval or until it reaches some threshold.

There are more scientific methods you could use, but this works well.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

` array 0 => float 52175.65502 1 => float 43303.23718` As you can see it's still not ideal (was hoping for an algorithm similar to K-Cluster). Thank you though.
On my tests with personal ranges from 0 to 16000, the difference is regularly less than 100 after 1000 iterations. Note that I am splitting up my original array as: 0,1, 1,0, 0,1. That is, team 1 gets the best player. Then team 2 gets two players. Then team 1 gets two players, etc.
Also, you may want to adjust the algorithm slightly to sometimes (with low probability) swap players, even if it makes the difference bigger. e.g. if (abs($new_diff) < abs($diff) || rand(0, 100) < 5)
OK I readjusted the values a bit and this is perfect! Thanks! Edit: I also recommend using mt_rand it's usually 4x faster :)
1

This is extremely simplistic, but have you considered just doing it like a draft? With the array sorted as in your example, Team A gets array[0], Team B gets array[1] and array[2] the next two picks go to Team A, and so on.

For the example you give, I got one team with ~50,000 and the other with ~45,000.

Improve this answer

1 Comment

Yup, but the problem is Team A would always be "better" (I've tried randomly iterating through Team B and swapping players but that wasn't really a solid solution... if I have to do it then I will, but I figured there's a much better solution to this).
0

I assume this is just a different scenario for the Bin Packing Problem. While different strategies may outperform others given different sets of data, my brain tends to favor First Fit Descending. I'm calling your associative array $pool. I'm setting a limit called $maxTrades to limit the data refining iterations and prevent an infinite loop. Essentially, you sort the player pool descending, perform an alternating split of the player pool, then make 1-for-1 trades which reduce the value difference between the teams until the teams are perfectly even or the iteraton limit is reached. Demo

function balanceTeams(array $pool, int $maxTrades = 10): array
{
    arsort($pool);
    $teams = [[], []];
    $i = 1;
    foreach ($pool as $k => $v) {
        $teams[$i = 1 - $i][$k] = $v;
    }

    $getDiff = fn($a, $b) => array_sum($a) - array_sum($b);

    for ($i = 0; $i < $maxTrades; ++$i) {
        $diff = $getDiff(...$teams);
        //echo "Diff: $diff\n";
        if (!$diff) {
            break;
        }

        foreach ($teams[0] as $idA => $valA) {
            foreach ($teams[1] as $idB => $valB) {
                if (abs($valA - $valB) < abs($diff)) {
                    $teams[0][$idB] = $valB;
                    $teams[1][$idA] = $valA;
                    unset($teams[0][$idA], $teams[1][$idB]);
                    arsort($teams[0]);
                    arsort($teams[1]);
                    //printf("Trade %d: %s for %s\n", $i + 1, $idA, $idB);
                    continue 3;
                }
            }
        }
        break;
    }

    return $teams;
}

var_export(balanceTeams($pool);

Summary (pretty not bad):

  • 47738.246250 average team value
  • 47739.963060 post-sort team 1 total
  • 47736.529440 post-sort team 2 total
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.