3

トーナメントのブラケット シートを生成するコードがあります。私にはプレーヤーがいて、各プレーヤーは学校に関連付けられています。同じ学校のプレーヤーの最初の試合 (または同じ学校の試合が可能な限り) がないように、配列をプレーヤーで並べ替える必要があります。

このようなもの：

$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.

上記の例では [0] と [1] は同じ学校なので一緒に行くことはできません。[0] は、たとえば 3 と一緒に使用できます。

usort を試していますが、これにアプローチする正しい方法がわかりません。

4

2 に答える 2

1

OK、問題を再検討した新しい回答。アルゴリズムは、次のようにする必要があると思います。

  • 割り当てられていないプレーヤーを反復処理します (このリストは一度に 2 つ減ることに注意してください)。
  • プレイヤーの現在のイテレーションがいるスクールではなく、残りのプレイヤーが最も多いスクールを見つけます。
  • 上記のチェックでプレイヤーがいる学校が見つからない場合は、プレイヤーの現在のイテレーションと同じ学校を使用することに頼ります。これにより、割り当てプールに他のプレイヤーが残っていない場合、同じ学校のプレイヤーが互いにプレイできるという効果があります。 .
  • 今見つけた学校から任意のプレイヤーを割り当てる
  • 現在反復されているプレーヤーと任意のプレーヤーをペアにする
  • プールから両方のプレーヤーを削除します

実装に関しては、2 つのインデックス (学校の 1 つとプレーヤーの 1 つ) を維持する方が簡単であることがわかりました。オブジェクトには本質的に参照性があるため、いくつかのクラスにまとめました。私のコードは以下のとおりです...そのままで動作しますが、微調整が必​​要な場合があります。

<?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);

出力は以下のとおりです。

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"
  }
}
于 2013-10-15T21:33:44.857 に答える