Split an array into two arrays of (ideally) even total value

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.

Solution

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.