Ten chess-players...
in [Mathematica]
|
Prev: How to format Superscript and Subscript for a symbol to the same vertical level??
Next: FromAdjacencyMatrix / FromAdjacencyLists - broken?
From: John Fultz on 26 Oct 2009 00:31 On Sat, 24 Oct 2009 02:38:47 -0400 (EDT), cmpbrn(a)gmail.com wrote: > Given 10 (1 to 10) chess-players, in one day they play 5 games (1-2, > 6-10, 5-7, 4-8, 3-9). > Then they need 8 more days to complete the championship (one gamer > must play one time against any other player): > 1-3, 2-10, 6-7, 5-8, 4-9 > 1-4, 2-3, 7-10, 6-8, 5-9 > 1-5, 2-4, 3-10, 7-8, 6-9 > 1-6, 2-5, 3-4, 7-9, 8-10 > 1-7, 2-6, 3-5, 4-10, 8-9 > 1-8, 2-7, 3-6, 4-5, 9-10 > 1-9, 2-8, 3-7, 4-6, 5-10 > 1-10, 2-9, 3-8, 4-7, 5-6 > > How can I get the 10*(10-1)/2 = 45 pairs distributed in the 9x5 > matrix? > What's about any other even number of players? > > Bruno I've done quite the same thing for Scrabble competitions. Here's an= algorithm for round robin pairing for any number of players: http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm And here's a simple function which implements the algorithm for a complete= round robin. For an odd number of players, just invent a "bye" player (bye's= opponent gets that round off) and pair as for even players. Pair[n_Integer?EvenQ] := Table[ Prepend[RotateRight[Range[n - 1] + 1, round - 1], 1][[{couple, -couple}]], {round, n - 1}, {couple, n/2}] An example output: In[28]:= Pair[8] // Grid Out[28]= {1,8}=09{2,7}=09{3,6}=09{4,5} {1,7}=09{8,6}=09{2,5}=09{3,4} {1,6}=09{7,5}=09{8,4}=09{2,3} {1,5}=09{6,4}=09{7,3}=09{8,2} {1,4}=09{5,3}=09{6,2}=09{7,8} {1,3}=09{4,2}=09{5,8}=09{6,7} {1,2}=09{3,8}=09{4,7}=09{5,6} Sincerely, John Fultz jfultz(a)wolfram.com User Interface Group Wolfram Research, Inc.
From: DrMajorBob on 10 Nov 2009 06:02 Here's a simple way to compute a round robin tournament: Clear[roundRobin] roundRobin[n_?EvenQ][k_Integer] /; 1 <= k < n := Transpose(a)Partition[Flatten@{1, RotateRight[Range[2, n], k - 1]}, n/2] roundRobin[n_?Positive][k_Integer] := roundRobin[n + 1][k] Ten players: Array[roundRobin[10], 9] {{{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}, {{1, 5}, {10, 6}, {2, 7}, {3, 8}, {4, 9}}, {{1, 4}, {9, 5}, {10, 6}, {2, 7}, {3, 8}}, {{1, 3}, {8, 4}, {9, 5}, {10, 6}, {2, 7}}, {{1, 2}, {7, 3}, {8, 4}, {9, 5}, {10, 6}}, {{1, 10}, {6, 2}, {7, 3}, {8, 4}, {9, 5}}, {{1, 9}, {5, 10}, {6, 2}, {7, 3}, {8, 4}}, {{1, 8}, {4, 9}, {5, 10}, {6, 2}, {7, 3}}, {{1, 7}, {3, 8}, {4, 9}, {5, 10}, {6, 2}}} 9 players: Array[roundRobin[9], 8] {{{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}, {{1, 5}, {10, 6}, {2, 7}, {3, 8}, {4, 9}}, {{1, 4}, {9, 5}, {10, 6}, {2, 7}, {3, 8}}, {{1, 3}, {8, 4}, {9, 5}, {10, 6}, {2, 7}}, {{1, 2}, {7, 3}, {8, 4}, {9, 5}, {10, 6}}, {{1, 10}, {6, 2}, {7, 3}, {8, 4}, {9, 5}}, {{1, 9}, {5, 10}, {6, 2}, {7, 3}, {8, 4}}, {{1, 8}, {4, 9}, {5, 10}, {6, 2}, {7, 3}}} Bobby On Sat, 24 Oct 2009 01:38:47 -0500, <cmpbrn(a)gmail.com> wrote: > Given 10 (1 to 10) chess-players, in one day they play 5 games (1-2, > 6-10, 5-7, 4-8, 3-9). > Then they need 8 more days to complete the championship (one gamer > must play one time against any other player): > 1-3, 2-10, 6-7, 5-8, 4-9 > 1-4, 2-3, 7-10, 6-8, 5-9 > 1-5, 2-4, 3-10, 7-8, 6-9 > 1-6, 2-5, 3-4, 7-9, 8-10 > 1-7, 2-6, 3-5, 4-10, 8-9 > 1-8, 2-7, 3-6, 4-5, 9-10 > 1-9, 2-8, 3-7, 4-6, 5-10 > 1-10, 2-9, 3-8, 4-7, 5-6 > > How can I get the 10*(10-1)/2 = 45 pairs distributed in the 9x5 > matrix? > What's about any other even number of players? > > Bruno > -- DrMajorBob(a)yahoo.com
From: DrMajorBob on 10 Nov 2009 06:03 I'm clearly slipping, as my previous solution fails. The one below does work, however. When n is odd, you solve the problem for n + 1, and the added player is fictitious; being paired with the dummy means you have a "bye" in the round. Clear[roundRobin, tournament] roundRobin[n_?EvenQ][1] := roundRobin[n][1] = Transpose@{Range[n/2], Range[n, n/2 + 1, -1]} roundRobin[n_?OddQ] := roundRobin[n + 1] roundRobin[n_?EvenQ][k_] /; k > 1 := roundRobin[n][k] = roundRobin[n][k - 1] /. Thread[Range[2, n] -> RotateRight[Range[2, n]]] tournament[n_?EvenQ] := Array[roundRobin[n], n - 1] tournament[n_?OddQ] := tournament[n + 1] tourney = tournament[10] {{{1, 10}, {2, 9}, {3, 8}, {4, 7}, {5, 6}}, {{1, 9}, {10, 8}, {2, 7}, {3, 6}, {4, 5}}, {{1, 8}, {9, 7}, {10, 6}, {2, 5}, {3, 4}}, {{1, 7}, {8, 6}, {9, 5}, {10, 4}, {2, 3}}, {{1, 6}, {7, 5}, {8, 4}, {9, 3}, {10, 2}}, {{1, 5}, {6, 4}, {7, 3}, {8, 2}, {9, 10}}, {{1, 4}, {5, 3}, {6, 2}, {7, 10}, {8, 9}}, {{1, 3}, {4, 2}, {5, 10}, {6, 9}, {7, 8}}, {{1, 2}, {3, 10}, {4, 9}, {5, 8}, {6, 7}}} Union @@ tourney == Sort@(Join @@ tourney) Binomial[10, 2] == Total[Length /@ tourney] True True tournament[9] == tournament[10] True The "memoization", e.g. "roundRobin[n_?EvenQ][1] := roundRobin[n][1] = ...." isn't necessary for a tournament of reasonable size, but I put it in anyway. If a tournament were large enough to make it necessary, it would be impractical to sponsor such a round robin at all. That's why chess tournaments are usually scheduled via the Swiss system or even an "accelerated" Swiss. Bobby On Mon, 09 Nov 2009 21:15:12 -0600, DrMajorBob <btreat1(a)austin.rr.com> wrote: > Here's a simple way to compute a round robin tournament: > > Clear[roundRobin] > roundRobin[n_?EvenQ][k_Integer] /; 1 <= k < n := > Transpose(a)Partition[Flatten@{1, RotateRight[Range[2, n], k - 1]}, n/2] > roundRobin[n_?Positive][k_Integer] := roundRobin[n + 1][k] > > Ten players: > > Array[roundRobin[10], 9] > > {{{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}, {{1, 5}, {10, 6}, {2, > 7}, {3, 8}, {4, 9}}, {{1, 4}, {9, 5}, {10, 6}, {2, 7}, {3, > 8}}, {{1, 3}, {8, 4}, {9, 5}, {10, 6}, {2, 7}}, {{1, 2}, {7, > 3}, {8, 4}, {9, 5}, {10, 6}}, {{1, 10}, {6, 2}, {7, 3}, {8, 4}, {9, > 5}}, {{1, 9}, {5, 10}, {6, 2}, {7, 3}, {8, 4}}, {{1, 8}, {4, > 9}, {5, 10}, {6, 2}, {7, 3}}, {{1, 7}, {3, 8}, {4, 9}, {5, 10}, {6, > 2}}} > > 9 players: > > Array[roundRobin[9], 8] > > {{{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}, {{1, 5}, {10, 6}, {2, > 7}, {3, 8}, {4, 9}}, {{1, 4}, {9, 5}, {10, 6}, {2, 7}, {3, > 8}}, {{1, 3}, {8, 4}, {9, 5}, {10, 6}, {2, 7}}, {{1, 2}, {7, > 3}, {8, 4}, {9, 5}, {10, 6}}, {{1, 10}, {6, 2}, {7, 3}, {8, 4}, {9, > 5}}, {{1, 9}, {5, 10}, {6, 2}, {7, 3}, {8, 4}}, {{1, 8}, {4, > 9}, {5, 10}, {6, 2}, {7, 3}}} > > Bobby > > On Sat, 24 Oct 2009 01:38:47 -0500, <cmpbrn(a)gmail.com> wrote: > >> Given 10 (1 to 10) chess-players, in one day they play 5 games (1-2, >> 6-10, 5-7, 4-8, 3-9). >> Then they need 8 more days to complete the championship (one gamer >> must play one time against any other player): >> 1-3, 2-10, 6-7, 5-8, 4-9 >> 1-4, 2-3, 7-10, 6-8, 5-9 >> 1-5, 2-4, 3-10, 7-8, 6-9 >> 1-6, 2-5, 3-4, 7-9, 8-10 >> 1-7, 2-6, 3-5, 4-10, 8-9 >> 1-8, 2-7, 3-6, 4-5, 9-10 >> 1-9, 2-8, 3-7, 4-6, 5-10 >> 1-10, 2-9, 3-8, 4-7, 5-6 >> >> How can I get the 10*(10-1)/2 = 45 pairs distributed in the 9x5 >> matrix? >> What's about any other even number of players? >> >> Bruno >> > > -- DrMajorBob(a)yahoo.com
From: DrMajorBob on 10 Nov 2009 06:03
And finally (I promise), here's a much nicer solution. It's far faster, uses no memoization, and makes "byes" explicit. Clear[roundRobinRotate, tournament] roundRobinRotate[lst_List] := Replace[lst, Thread[Range[2, 2 Length(a)lst] -> RotateRight[Range[2, 2 Length(a)lst]]], {2}] tournament[n_?EvenQ] := NestList[roundRobinRotate, Transpose@{Range[n/2], Range[n, n/2 + 1, -1]}, n - 2] tournament[n_?OddQ] := tournament[n + 1] /. n + 1 :> "Bye" tournament[10] {{{1, 10}, {2, 9}, {3, 8}, {4, 7}, {5, 6}}, {{1, 9}, {10, 8}, {2, 7}, {3, 6}, {4, 5}}, {{1, 8}, {9, 7}, {10, 6}, {2, 5}, {3, 4}}, {{1, 7}, {8, 6}, {9, 5}, {10, 4}, {2, 3}}, {{1, 6}, {7, 5}, {8, 4}, {9, 3}, {10, 2}}, {{1, 5}, {6, 4}, {7, 3}, {8, 2}, {9, 10}}, {{1, 4}, {5, 3}, {6, 2}, {7, 10}, {8, 9}}, {{1, 3}, {4, 2}, {5, 10}, {6, 9}, {7, 8}}, {{1, 2}, {3, 10}, {4, 9}, {5, 8}, {6, 7}}} Union @@ tourney == Sort@(Join @@ tourney) Binomial[10, 2] == Total[Length /@ tourney] True True tournament[9] {{{1, "Bye"}, {2, 9}, {3, 8}, {4, 7}, {5, 6}}, {{1, 9}, {"Bye", 8}, {2, 7}, {3, 6}, {4, 5}}, {{1, 8}, {9, 7}, {"Bye", 6}, {2, 5}, {3, 4}}, {{1, 7}, {8, 6}, {9, 5}, {"Bye", 4}, {2, 3}}, {{1, 6}, {7, 5}, {8, 4}, {9, 3}, {"Bye", 2}}, {{1, 5}, {6, 4}, {7, 3}, {8, 2}, {9, "Bye"}}, {{1, 4}, {5, 3}, {6, 2}, {7, "Bye"}, {8, 9}}, {{1, 3}, {4, 2}, {5, "Bye"}, {6, 9}, {7, 8}}, {{1, 2}, {3, "Bye"}, {4, 9}, {5, 8}, {6, 7}}} Bobby On Sat, 24 Oct 2009 01:38:47 -0500, <cmpbrn(a)gmail.com> wrote: > Given 10 (1 to 10) chess-players, in one day they play 5 games (1-2, > 6-10, 5-7, 4-8, 3-9). > Then they need 8 more days to complete the championship (one gamer > must play one time against any other player): > 1-3, 2-10, 6-7, 5-8, 4-9 > 1-4, 2-3, 7-10, 6-8, 5-9 > 1-5, 2-4, 3-10, 7-8, 6-9 > 1-6, 2-5, 3-4, 7-9, 8-10 > 1-7, 2-6, 3-5, 4-10, 8-9 > 1-8, 2-7, 3-6, 4-5, 9-10 > 1-9, 2-8, 3-7, 4-6, 5-10 > 1-10, 2-9, 3-8, 4-7, 5-6 > > How can I get the 10*(10-1)/2 = 45 pairs distributed in the 9x5 > matrix? > What's about any other even number of players? > > Bruno > -- DrMajorBob(a)yahoo.com |