0

这是我的第一个问题。我试图找到答案 2 天，但我找不到我要找的东西。

问题：我怎样才能最大限度地减少来自同一所学校的学生之间的匹配量

我有一个非常实际的案例，我需要安排一场比赛（锦标赛支架），但有些参赛者可能来自同一所学校。来自同一学校的学生应尽可能远离彼此

例如：{AAABBC} => {AB}、{AC}、{AB}

如果一所学校的参与者超过一半，那么除了将同一学校的两个人配对之外别无他法。

例如：{AAAABC} => {AB}、{AC}、{AA}

我不希望获得代码，只是一些关键字或一些伪代码，您认为这将是一种非常有用的方法！

我尝试深入研究约束解决算法和锦标赛括号算法，但他们没有考虑最小化同一学校学生之间的比赛数量。

好吧，非常感谢您！

4

3 回答 3

0

一个简单的算法（编辑 2）

从下面的评论：你有一个单场淘汰赛。您必须在锦标赛括号中选择玩家的位置。如果您查看您的分组，您会看到：球员，还有球员对（在第 1 场比赛中相互对战的球员）、球员对（第 1 场比赛的获胜者与第 2 场比赛的获胜者）、等等。

这个想法

  • 按学校对学生进行排序，学生多的学校排在学生少的学校之前。例如 ABBBBCC -> BBBBCC A。
  • 将学生分成两组 A 和 B，就像在战争纸牌游戏中一样：A 中的第 1 名学生，B 中的第 2 名学生，A 中的第 3 名学生，B 中的第 4 名学生，...
  • 继续 A 组和 B 组。

您有一个递归：玩家在级别 k-1（k=n-1 到 0）中的位置是((pos at level k) % 2) * 2^k + (pos at level k) // 2（每个偶数都向左，每个奇数向右）

Python代码

按学校数量排序数组：

assert 2**math.log2(len(players)) == len(players) # n is the number of rounds
c = collections.Counter([p.school for p in players])
players_sorted_by_school_count = sorted(players, key=lambda p:-c[p.school])

求每个玩家的最终位置：

players_sorted_for_tournament = [-1] * 2**n
for j, player in enumerate(players_sorted_by_school_count):
    pos = 0
    for e in range(n-1,-1,-1):
        if j % 2 == 1:
            pos += 2**e # to the right
        j = j // 2
    players_sorted_for_tournament[pos] = player

这应该给足够多样化的群体，但我不确定它是否是最佳的。等待评论。

第一个版本：如何让不同学校的学生结对

只需将同一所学校的学生放在一个堆栈中即可。你有和学校一样多的堆栈。现在，按学生人数对您的堆栈进行排序。在你的第一个例子{A A A B B C}中，你得到：

A
A B
A B C

现在，从前两个堆栈中取出两个顶部元素。堆栈大小已更改：如果需要，重新排序堆栈并继续。当你只有一个筹码时，从这个筹码中组成对子。

这个想法是尽可能长时间地保留尽可能多的“学校堆栈”：你让学生们远离小堆栈，直到你别无选择，只能接受他们。

第二个示例的步骤{A A A A B C}：

A
A
A
A B C => output A, B

A
A
A C => output A, C

A
A => output A A

这是一个匹配问题（编辑 1）

我详细说明下面的评论。你有一个单场淘汰赛。您必须在锦标赛括号中选择玩家的位置。如果您查看您的分组，您会看到：球员，还有球员对（在第 1 场比赛中相互对战的球员）、球员对（第 1 场比赛的获胜者与第 2 场比赛的获胜者）、等等。

您的解决方案是从所有玩家的集合开始，并将其分成尽可能多样化的两组。“多样化”在这里是指：不同学校的最大数量。为此，您检查将集合分成两个大小相等的子集的所有可能的元素组合。然后你在这些集合上递归地执行相同的操作，直到你到达玩家级别。

另一个想法是从玩家开始，并尝试与其他学校的其他玩家配对。让我们定义一个距离：如果两个玩家在同一所学校，则为 1，如果他们在不同学校，则为 0。您想以最小的全局距离配对。

这个距离可以推广到成对的玩家：取普通学校的数量。即：ABAB -> 2 (A & B), ABAC -> 1 (A), ABCD -> 0。可以想象两组之间的距离（玩家，对，对对，...）：数的普通学校。现在您可以将其视为一个图，其顶点是集合（玩家、对、对对……），其边连接每对顶点的权重为上面定义的距离。您正在寻找具有最小权重的完美匹配（所有顶点都匹配）。

开花算法或它的一些变体似乎符合您的需求，但如果玩家数量有限，它可能会有点矫枉过正。

于 2018-04-26T06:06:08.733 回答
0

创建一个二维数组，其中第一个维度将针对每个学校，第二个维度将针对此起飞的每个参与者。加载它们，您将线性获得所需的一切。例如：

学校 1 -------- 学校 2 -------- 学校 3

A ------------ B ------------- C

A ------------ B ------------- C

A ------------ B ------------- C

A ------------ 乙

A ------------ 乙

一种

一种

在上面的示例中，我们将有 3 所学校（第一维度），学校 1 有 7 名参与者（第二维度），学校 2 有 5 名参与者，学校 3 有 3 名参与者。您还可以创建包含结果组合的第二个数组，并且对于每个选择的对，在循环中从初始数组中删除该对，直到它完全为空并且结果数组完全充满。

于 2018-04-26T06:08:25.470 回答
0

我认为这个答案中的算法可能会有所帮助。

基本上：按学校对学生进行分组，并使用Bresenham 算法背后的错误跟踪思想将学校分布得尽可能远。然后你从列表中取出对。

于 2018-04-26T19:33:29.777 回答