PHP以两个为一组排序数组，避免合并具有相同值的项目

Question

I have a code to generate bracket sheets for a tournament. I have players and each player is associated with an school. I need to sort an array with the players so there no first matches of players of the same school (or the lower same-school matches possible).

Something like this:

$players = array( 
             array('name' => 'juan', 'school' => 'ABC'),   // 0
             array('name' => 'leo', 'school' => 'ABC'),    // 1
             array('name' => 'arnold', 'school' => 'DEF'), // 2
             array('name' => 'simon', 'school' => 'DEF'),  // 3
             array('name' => 'luke', 'school' => 'ECD'),   // 4
             array('name' => 'ash', 'school' => 'ECD'),    // 5
           );
// code to sort here

array_chunk($players, 2); // this generate an array with groups of two for matches.

In the above example [0] and [1] cant go together because they are on the same school. [0] can go with 3, for example.

I'm trying with usort, but I'm not sure what's the right way to approach this.

Answer 1

Ok, a new answer having re-examined the issue. The algorithm, I think, should be thus:

• Iterate over unallocated players (noting that this list reduces 2 at a time).
• Find the school with the most available remaining players which is not the school the current iteration of player is in.
• If the above check does not find a school with any players, resort to using the same school as the current iteration of player is in. This has the effect that players in the same school can play eachother if no other players remain in the allocation pool.
• Allocate an arbitrary player from the school we just found
• Pair the currently iterated player and the arbitrary player
• Remove both players from the pool

Implementation-wise, I found it easier to maintain 2 indexes - one of schools and 1 of players. I bundled it into a couple of classes because the inherently referential nature of objects makes life easier. My code is below... it works out of the box but may need some tweaking.

<?php

class School {
        protected $name;
        protected $players = [];

        public function __construct($name) {
                $this->name = $name;
        }

        public function get_name() {
                return $this->name;
        }

        public function add_player($name) {
                $this->players[] = $name;
        }

        public function del_player($name) {
                if (($index = array_search($name, $this->players)) !== false) {
                        unset($this->players[$index]);
                }
        }

        public function player_count() {
                return count($this->players);
        }

        public function get_player() {
                if (!reset($this->players)) {
                        return false;
                }

                return [
                        'school' => $this->name,
                        'name' => reset($this->players),
                ];
        }
}

class Players {
        protected $schools_index = [];
        protected $player_index = [];

        public function add_player($school, $player) {
                // Create school if not exists
                if (!isset($this->schools_index[$school])) {
                        $this->schools_index[$school] = new School($school);
                }

                // Add player to school and own index
                $this->schools_index[$school]->add_player($player);
                $this->player_index[$player] = $school;
        }

        public function del_player($school, $player) {
                // From school index
                $this->schools_index[$school]->del_player($player);

                // From own index
                if (isset($this->player_index[$player])) {
                        unset($this->player_index[$player]);
                }
        }

        public function biggest_school($exclude = null) {
                $rtn = null;

                // Find school excluding the exclude. Don't get schools with nobody left in them.
                foreach ($this->schools_index as $name=>$school) {
                        if ((!$exclude || $name != $exclude) && ($school->player_count()) && (!$rtn || $rtn->player_count() < $school->player_count())) {
                                $rtn = $school;
                        }
                }

                // If we didn't get a school, shitcan the exclude and try the excluded school
                if (!$rtn && $exclude) {
                        if ($this->schools_index[$exclude]->player_count()) {
                                $rtn = $this->schools_index[$exclude];
                        }
                }

                return $rtn;
        }

        public function get_player() {
                if (!reset($this->player_index)) {
                        return false;
                }

                return [
                        'school' => reset($this->player_index),
                        'name' => key($this->player_index),
                ];
        }

        public static function from_players_arr(array $players) {
                $obj = new static();

                foreach ($players as $player) {
                        // Add to indexes
                        $obj->add_player($player['school'], $player['name']);
                }

                return $obj;
        }
}

$players = array(
        array('name' => 'juan', 'school' => 'ABC'),
        array('name' => 'leo', 'school' => 'ABC'),
        array('name' => 'arnold', 'school' => 'ABC'),
        array('name' => 'simon', 'school' => 'ABC'),
        array('name' => 'luke', 'school' => 'ABC'),
        array('name' => 'alan', 'school' => 'JKL'),
        array('name' => 'jeff', 'school' => 'BAR'),
        array('name' => 'paul', 'school' => 'FOO'),
);

$players_obj = Players::from_players_arr($players);

$pairs = [];

while ($player = $players_obj->get_player()) {
        $players_obj->del_player($player['school'], $player['name']);

        $opponent = $players_obj->biggest_school($player['school'])->get_player();

        $pairs[] = [
                $player['name'],
                $opponent['name'],
        ];

        $players_obj->del_player($opponent['school'], $opponent['name']);
}

var_dump($pairs);

Output is below:

array(4) {
  [0] =>
  array(2) {
    [0] =>
    string(4) "juan"
    [1] =>
    string(4) "alan"
  }
  [1] =>
  array(2) {
    [0] =>
    string(3) "leo"
    [1] =>
    string(4) "jeff"
  }
  [2] =>
  array(2) {
    [0] =>
    string(6) "arnold"
    [1] =>
    string(4) "paul"
  }
  [3] =>
  array(2) {
    [0] =>
    string(5) "simon"
    [1] =>
    string(4) "luke"
  }
}