2

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

就我而言，我有 17 名参赛者，并希望他们以 3 或 4 名选手的形式进行比赛。我想有一种方法来生成 S，一组 P（玩家）的子集，使得 P 的每个元素与 P 的每个其他元素出现在 S 的至少一个元素中。

起初我认为平衡比赛设计会回答问题，但它似乎没有任何方法可以在每轮比赛中匹配多个参赛者，每对只能进行多次额外的对峙。

它也有一个确切的封面问题的味道，但不完全是。

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

4

2 回答 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 连续玩他/她的所有游戏，然后必须等待剩余的比赛）。

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

于 2015-03-09T20:41:18.790 回答
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])
于 2017-04-02T16:47:27.650 回答