寻找一组有n个参与者和m个参与者的匹配的算法

I have the following problem:

我有以下问题:

A group of n players wants to play a set of matches. Each match has m participants. I want to find a schedule with a minimum number of games where every player meets every other player at least once and maximum variety of opponents.

一组n个玩家想要玩一套游戏。每场比赛有m名参赛者。我想要找到一个时间表，在这个时间表上，每个玩家至少要和其他玩家相遇一次，并且要有最大的多样性。

After some research I found that the "social golfer problem" seems to be a similar problem but I could not find a solution which I could adapt nor can I come up with an own solution.

经过一些研究，我发现“社会高尔夫问题”似乎是一个类似的问题，但我找不到一个我可以适应的解决方案，也找不到自己的解决方案。

2 个解决方案

#1

Pseudocode (assuming there are flags inside the players):

伪代码(假设玩家内部有标志):

function taking array of players (x) and players per game (y) {    array of players in this game (z)    for each player (t) in x {        if z.length == y {break out of loop}        check the flag of each player in (t), if the flag is not set {            check if z.length is less than y {                set flag and add it to array z            }        }    }    if z.length is less than 2, change the players in z's flags back to false    return (if z.length == 3, return z, or else return false);}

Start with player A; (assume players A to F, 3 players per game)

开始与球员;(假设球员A到F，每场3人)

By going through from top to bottom, we can eliminate possibilities. Start with each person playing all other players (that they have not already played, so for example, B skips C because B played with C in ABC) (in groups of 3). We can write a function to do this (see psuedocode at top)

从上到下，我们可以消除可能性。首先让每个人扮演所有其他玩家(他们还没有玩过，例如，B跳过C，因为B在ABC中与C一起玩)(以3为一组)。

A B C (save this game to a list of games, or increment a counter or something)A D EA F -missing (returned false so we did not save this)B D E B F -missingC D EC F -missing D E F

Now, almost all players have played each other, if you only count the groups of 3. This is 5 games so far. Remove the games we've already counted, resulting in

现在，几乎所有的玩家都是互相比赛的，如果你只算3组的话。到目前为止这是5场比赛。删除我们已经计算过的游戏，结果是

A F -missingB F -missingC F -missing

What is in common here? They all have F. That means that F must play everyone in this list, so all we need to do is put F in the front.

这里有什么共同之处?它们都有F，这意味着F必须在这个列表中扮演每个人，所以我们要做的就是把F放在前面。

We can now do F A B, and then C F + any random player. This is the minimum 7 games.

我们现在可以做F A B，然后C F +任意一个随机玩家。这至少是7场比赛。

Basically, you can run the pseudocode over and over until it returns false 2 times in a row. When it has returned false 2 times in a row, you know that all flags have been set.

基本上，您可以一次又一次地运行伪代码，直到它连续两次返回false。当它连续两次返回false时，您就知道所有的标志都已设置。

#2

This may not be a complete solution, but... Consider a graph with n nodes. A match with m players can be represented by laying m-1 edges into the graph per round. The requirement that each player meet each other player at least once means that you will after some number of rounds have a complete graph.

这可能不是一个完整的解决方案，但是……考虑一个有n个节点的图。与m球员的比赛可以用每轮在图中放置m-1条边来表示。要求每个玩家至少与其他玩家见面一次，意味着你将在一些回合之后拥有一个完整的图表。

For round (match) 1, lay an arbitrary set of m-1 edges. For each next round, lay m-1 edges that are not currently connecting two nodes. Repeat until the graph is complete.

对于圆形(匹配)1，放置一组任意的m-1边。对于下一轮，在m-1边缘上画出目前没有连接两个节点的边。重复，直到图形完成。

Edit: Edges would need to be laid connected to ensure only m players are in a match for m-1 edges, which would make this a little more difficult. If you lay each round in a walk of the complete graph, the problem is then the same as finding the shortest walk of the complete graph. This answer to a different question may be relevant, and suggests the Floyd-Warshall algorithm.

编辑:需要将边缘连接起来，以确保m-1边缘的匹配中只有m个玩家，这将使这更加困难。如果你把每一个圆放在一个完整的图中，那么问题就和找到一个完整图中最短的路径一样。这个对不同问题的答案可能是相关的，并且建议Floyd-Warshall算法。

#1