什么算法可以为两个以上参赛者的回合生成循环"pairings"？

Question

我希望能够生成一组锦标赛对位，这样每个玩家至少面对另一个玩家一次，每个玩家玩相同数量的游戏。可以把它看作是《马里奥赛车》的循环对位的抽象。

在我的例子中，我有17个参赛者，并且希望他们在3或4人的回合中进行比赛。我想找到一种生成S的方法，P的子集(参与者)的集合使得P的每个元素与P的其他元素至少出现在S的一个元素中

一开始我认为一个平衡的比赛设计可以回答这个问题，但它似乎没有任何方法来匹配每个回合的多个参赛者，只是为每对增加多个对峙。

这也有点像一个确切的封面问题，但不完全是。

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

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连续玩了所有游戏，然后不得不等待剩余的比赛)。

虽然这应该解决你的问题，因为它目前的定义，我也会感兴趣的更好的方法，增加公平性(减少连续比赛的每个玩家)。

Answer 2

我尝试着为12名玩家/4名玩家做一些类似的事情，即每个玩家必须在5回合内与所有其他玩家进行游戏。不幸的是，我的解决方案只适用于7轮。我感兴趣的是自己解决N个玩家和每场比赛M个玩家的问题。

https://gist.github.com/anonymous/e3372d1e61b01cf453dc26a488c9e345

(ns tournament-gen.core)
(defn rotate [n ps]
  (concat (drop n ps) (take n ps)))
(defn round [size ps]
  (apply mapcat vector (partition (Math/floorDiv (count ps) size) ps)))
(defn rounds [size n ps]
  (take n (iterate #(rotate 2 (round size %)) ps)))
(defn set->map [gset]
  (into {}
        (for [k gset]
          [k gset])))
(defn verify [size gs]
  (apply merge-with
         clojure.set/union
         (for [game (mapcat (partial partition size) gs)]
           (set->map (set game)))))
; I got it to work in 7 rounds for 12, but it seems like 5 should be possible
(map (partial partition 4) (rounds 4 7 (range 0 12)))
;result
(((0 1 2 3) (4 5 6 7) (8 9 10 11))
 ((6 9 1 4) (7 10 2 5) (8 11 0 3))
 ((2 11 9 7) (5 0 1 10) (8 3 6 4))
 ((1 3 11 5) (10 6 9 0) (8 4 2 7))
 ((9 4 3 10) (0 2 11 6) (8 7 1 5))
 ((11 7 4 0) (6 1 3 2) (8 5 9 10))
 ((3 5 7 6) (2 9 4 1) (8 10 11 0)))
(sort-by first (into {} (for [[k v] (verify 4 (rounds 4 5 (range 0 12)))]
    [(str "Player " k) (count v)])))
=>
(["Player 0" 10]
 ["Player 1" 12]
 ["Player 10" 12]
 ["Player 11" 11]
 ["Player 2" 12]
 ["Player 3" 11]
 ["Player 4" 10]
 ["Player 5" 11]
 ["Player 6" 12]
 ["Player 7" 10]
 ["Player 8" 12]
 ["Player 9" 11])