algorithm - 对于超过两名参赛者的回合，什么算法可以生成循环赛 "pairings"？

Question

我希望能够生成一组锦标赛对决，使每个玩家至少面对一次其他玩家，每个玩家玩相同数量的游戏。将其视为马里奥赛车循环赛的抽象。

在我的例子中，我有 17 名参赛者，并且希望他们以 3 或 4 人为一组进行比赛。我想要一种生成 S 的方法，S 是 P(玩家)的一组子集，这样 P 的每个元素都至少出现在 S 的一个元素中，同时出现在 P 的每个其他元素中。

起初我以为一个平衡的锦标赛设计会回答，但它似乎没有任何办法可以在每轮比赛中匹配多个参赛者，只是为每对比赛增加多次对决。

它也有精确覆盖问题的味道，但不完全是。

这也适用于四人象棋、冰屋、各种纸牌和骰子游戏等游戏。

Answer 1

我刚刚为此创建了一个算法，但它确实有其缺点。如果 P 是玩家数量，C 是每场比赛的参赛者数量，我的算法只是创建一个大小为 C 的数组，其中我保存当前游戏中每个玩家的索引。

我首先用尽可能低的索引填充数组，其中每个索引仍大于前一个索引 ([1, 2, 3])。在每一轮中，我从数组的后面开始并尝试增加玩家索引。当我超出界限时，我向左移动一步，增加该玩家索引并将所有后续玩家设置为可能的最低值，同时仍保持每个索引大于前一个索引。

所以每轮有 5 名玩家和 3 名参赛者，我得到

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4] <- could not increase 3rd position, increase 2nd position
[1, 3, 5]
[1, 4, 5] <- could not increase 3rd position, increase 2nd position
[2, 3, 4] <- could not increase 3rd or 2nd position, increase 1st position
[2, 3, 5]
[2, 4, 5] <- could not increase 3rd position, increase 2nd position
[3, 4, 5] <- could not increase 3rd or 2nd position, increase 1st position
---------
could not increase any position -> done

这个问题很明显；玩家在游戏中的分布并不公平，相反，许多玩家不得不连续玩不必要的游戏(特别是，玩家 1 连续玩他/她的所有游戏，然后必须等待锦标赛的剩余部分)。

虽然这应该可以解决您当前定义的问题，但我也对一种提高公平性的更好方法感兴趣(每个玩家的连续游戏较少)。