3

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.

sehrgut
  • 209
  • 1
  • 13
  • 1
    This question appears to be off-topic because this site is for practical programming problems, not algorithms. Maybe maths or CS would be a better venue – Damien_The_Unbeliever Jun 20 '14 at 17:07
  • 2
    I don't think it's OT. There are a large number of tournament scheduling algorithm questions on here, and they were not judged OT. I checked that before I posted. – sehrgut Jun 20 '14 at 17:45
  • Is this perhaps what you're looking for? http://stackoverflow.com/questions/6648512/scheduling-algorithm-for-a-round-robin-tournament – Jim Mischel Jun 20 '14 at 19:12
  • @JimMischel Unfortunately not. That's a question regarding the classic pairwise match tournament. What I'm looking for is a way to gerneralize that to n participants per match (rather than just 2). There's a huge amount of mathematical literature on the special case of n=2, simply because it lends itself to things like graph analysis (where each participant is a node, and each match is an edge) that aren't applicable to subsets of any cardinality other than 2. Thanks, though! – sehrgut Jun 20 '14 at 19:41
  • 1
    Seeing this is unanswered 9 months later; did you by any chance find a good algorithm? – JHH Mar 09 '15 at 20:14
  • Not yet, but your answer below looks intriguing. I'll be trying it out in a bit. – sehrgut Mar 10 '15 at 19:56

2 Answers2

1

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

JHH
  • 8,567
  • 8
  • 47
  • 91
  • That's an interesting approach. I'll mock it up today or tomorrow, but I don't know that the order in which solutions are enumerated is much of an issue, since I do only need a set, not a sequence, of matchups. Edit: I'm not sure this has the potential to reach all possible matchups, though, so there could be some bias that isn't immediately apparent. I'll have to work that out separately. – sehrgut Mar 10 '15 at 19:54
  • 1
    @sehrgut I posted http://stackoverflow.com/questions/28965908/algorithm-for-generating-anti-gray-on-demand-combinations-of-k-elements-from-n that may be of interest to you as well. – JHH Mar 11 '15 at 14:16
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])
Brian Baritonehands Gregg
  • 376
  • 2
  • 4