对于有两名以上参赛者的轮次，什么算法可以生成Round-Robin“配对”？

2 回答

• 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连续玩他/她的所有游戏，然后必须等待比赛的剩余部分） .

  虽然这应该可以解决您目前定义的问题，但我也会对更好的方法感兴趣，同时提高公平性（每个玩家的连续游戏次数减少） .

  回复于 2024-04-29T04:18:28+08:00
• 1

  我试图为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])
  

  回复于 2024-04-29T04:18:28+08:00