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

好的，重新检查了这个问题的新答案。我认为算法应该是这样的：

  • 遍历未分配的玩家（注意这个列表一次减少 2 个）。
  • 找到拥有最多可用剩余玩家的学校，而不是当前玩家迭代所在的学校。
  • 如果上述检查没有找到有任何玩家的学校，请使用与当前玩家迭代所在的学校相同的学校。这样的效果是，如果分配池中没有其他玩家，同一学校的玩家可以互相玩.
  • 从我们刚刚找到的学校分配任意玩家
  • 将当前迭代的播放器和任意播放器配对
  • 将两名玩家从池中移除

在实施方面，我发现维护 2 个索引更容易 - 一个学校和 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 回答
0

我们要做的是将球员分成两组：竞争者 1 和竞争者 2。我们将用同一学校的连续球员填补竞争者 a：

如果为了简洁起见，我们将学校命名为一个字母，那么我们基本上拥有的是：

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

或者，如果我们翻转它，它会变得更清晰：

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

如果一所学校的球员人数超过总人数的一半怎么办？走着瞧：

 A A A A A
 A B B C D

所以：

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

我在这里作弊了一点：我首先从最大的学校挑选了球员。但是，只要我们将学校分组在一起，它仍然有效。让我们来看看我的输出$a = range('A','F'); shuffle($a):，结果是：FCADBE，它给了我们：

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

.. 这也适用于 A > half：

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

让我们把它分成几部分。我们要做的是：

  1. 按学校对球员进行排序
  2. 将此排序后的数组分成 2 组。
  3. 按顺序添加第一组和第二组中的一个来创建对。

减少它的好处是你可以找到答案：

  1. 关于 SO 的数百个问题
  2. 这是一个很好的答案
  3. 我们可以使用MultiIterator，这将是一个合乎逻辑（且有效）的选择，但我将向您展示另一种创建 2 个数组对（如果您有 3 个数组，则为三元组等）的简短方法

所以，让我们这样做：

 //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现在有了您输入的内容：

[
    [
        {
            "name": "juan",
            "school": "ABC"
        },
        {
            "name": "arnold",
            "school": "DEF"
        }
    ],
    [
        {
            "name": "leo",
            "school": "ABC"
        },
        {
            "name": "ash",
            "school": "ECD"
        }
    ],
    [
        {
            "name": "simon",
            "school": "DEF"
        },
        {
            "name": "luke",
            "school": "ECD"
        }
    ]
]
于 2013-10-15T22:49:07.213 回答