PHP Sort array in groups of two avoiding merge of items with same values

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.

phil-lavin · Accepted Answer · 2013-10-15 21:33:44Z

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"
  }
}

Community · Accepted Answer · 2017-05-23 12:21:08Z

What we are going to do, is split the players in 2 groups: contenders 1 & contenders 2. We're going to fill contenders a with consecutive players of the same school:

If we name the schools a single letter for brevity, what we'll essentially have is:

 A A A A B B B C
 C C D D E E F F

Or, if we flip it, it becomes clearer:

 A C
 A C
 A D
 A D
 B E
 B E
 B F
 C F

What happens if one school has > the half of the total number of players? Well, let's see:

 A A A A A
 A B B C D

So:

 A A <= one A vs. A, which is unavoidable, but the method still works.
 A B
 A B
 A C
 A D

I cheated a bit here: I sorted out the players from the biggest school first. It however still works as long as we group schools together. Let's take my output of $a = range('A','F'); shuffle($a):, which here resulted in: FCADBE, which gives us:

 F A
 F D
 C D
 C B
 C B
 A B
 A E
 A E

.. which works, also for A > half:

 C A
 A A <= that one double again, unavoidable
 A D
 A B
 A B

Let's break this into parts. What we have to do is:

sort the players by school
break this sorted array into 2 groups.
create pairs by adding on from the first group & one from the second group, in order.

The advantage of cutting it down is so you can find answers:

hundreds of questions on SO
this is a nice answer
We could use a MultiIterator, which would be a logical (and working) choice, but I'll show you another short way of creating pairs of 2 arrays (or triplets if you have 3 arrays, etc.)

So, let's do that:

 //sort by school
 $players = ... your array ...
 usort($players,function($playerA, $playerB){
     return strcmp($playerA['school'], $playerB['school']);
 });
 //voila, sorted

 //break this into 2 groups:
 $size = ceil(count($players) / 2); // round UP
 $groupA = array_slice($players,0,$size);
 $groupB = array_slice($players,$size);

 //create our duels array:
 $duels = array_map(null, $groupA, $groupB);

$duels now has this content with your input:

[
    [
        {
            "name": "juan",
            "school": "ABC"
        },
        {
            "name": "arnold",
            "school": "DEF"
        }
    ],
    [
        {
            "name": "leo",
            "school": "ABC"
        },
        {
            "name": "ash",
            "school": "ECD"
        }
    ],
    [
        {
            "name": "simon",
            "school": "DEF"
        },
        {
            "name": "luke",
            "school": "ECD"
        }
    ]
]

Collectives™ on Stack Overflow

PHP Sort array in groups of two avoiding merge of items with same values

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related