优化 - 将参与者分布在彼此远离的地方

Question

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

问：如何尽量减少同一学校学生之间的匹配次数

我有一个非常实际的案例，我需要安排一场比赛（锦标赛）但有些参与者可能来自同一所学校。同校的尽量放远一些

例如：{A A A B B C} => {A B}，{A C}，{A B}

如果一所学校的人数超过半数，那就没办法了，只能让同一所学校的2个人配对。

例如：{A A A A B C} => {A B}、{A C}、{A A}

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

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

好的，先谢谢你了！

Answer 1

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

来自下面的评论：您参加的是单场淘汰赛。您必须选择选手在锦标赛组别中的位置。如果你查看你的组别，你会看到：玩家，还有玩家对（玩家在第 1 场比赛中相互对抗），玩家对（第 1 对的胜者对第 2 对的胜者进行第 2 场比赛），等等。

想法

按学校对学生进行排序，学生多的学校在学生少的学校之前。例如 A B B B B C C -> B B B B C C A.
将学生分成 A 组和 B 组，如 war 纸牌游戏：A 组第 1 名学生，B 组第二名学生，A 组第三名学生，B 组第四名学生，...
继续 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

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

我们的想法是尽可能多地保留 "schools-stacks" 尽可能长的时间：你可以让小筹码的学生省下来，直到你别无选择，只能拿走他们。

第二个示例的步骤，{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 对的胜者进行第 2 场比赛），等等。

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

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

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

blossom algorithm 或其某些变体似乎可以满足您的需求，但如果玩家数量有限，这可能有点矫枉过正。

Answer 2

创建一个二维数组，其中第一个维度代表每所学校，第二个维度代表这次起飞的每个参与者。加载它们，您将拥有线性所需的一切。例如：

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

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

A ---------- B

一个

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

Answer 3

我认为中的算法可以提供帮助。

基本上：按学校分组，利用Bresenham's Algorithm背后的error tracking思想，将学校分布的尽可能远。然后你从列表中取出一对。

优化 - 将参与者分布在彼此远离的地方

Optimization - distribute participants far from each other

algorithm

optimization

match

tournament

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

想法

Python代码

第一版：不同学校的学生如何配对

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