What algorithm can generate Round-Robin "pairings" for rounds with more than two contestants?

Question

I'd like to be able to generate a set of tournament match-ups such that each player faces each other player at least once, each player plays the same number of games. Think of it as an abstraction of round-robin matchups to Mario Kart.

In my case, I have 17 contestants, and would like them to play in rounds of 3 or 4 players. I'd like to have a way to generate S, a set of subsets of P (players) such that each element of P occurs in at least one element of S with each other element of P.

At first I thought a Balanced Tournament Design would answer, but it doesn't seem to have any way to match multiple contestants per round, just multiple additional face-offs for each pair.

It also smacks of an exact cover problem, but not quite.

This would be applicable to games such as four-player chess, icehouse, various card and dice games, and the like as well.

Answer 1

I was trying to do something similar for 12 players/4 per game where each player has to play all other players over 5 rounds. Unfortunately, my solution only worked for 7 rounds. I'm interested in solving this myself for N players and M per game.

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])

Answer 2

I've just created an algorithm for this, but it does have its shortcomings. If P is the number of players, and C the number of contestants in each game, my algorithm simply creates an array the size of C in which I keep the indices of each player in the current game.

I start by filling the array with the lowest possible indices where each index is still larger than the previous one ([1, 2, 3]). In each round I start from the back of the array and try to increment the player index. When I reach out of bounds I move one step to the left, incrementing that player index and setting all the following players to their lowest possible value while still keeping each index larger than the previous one.

So for 5 players and 3 contenstants in each round I get

[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

The problem with this is obvious; players are not distributed fairly across games, but rather, many players have to play an unnecessary number of consecutive games (in particular, player 1 plays all his/her games in succession and then has to wait for the remainder of the tournament).

While this should solve your problem as it's currently defined, I too would be interested in a better approach with increased fairness (less consecutive games for each player).