Re: Ten chess-players...
- To: mathgroup at smc.vnet.net
- Subject: [mg99315] Re: [mg99269] Ten chess-players...
- From: Leonid Shifrin <lshifr at gmail.com>
- Date: Sat, 2 May 2009 06:01:44 -0400 (EDT)
- References: <36a5dba2-11b9-45df-84c3-9e712e47fec9@q33g2000pra.googlegroups.com>
Hi,
If I understand correctly, you would like to find some player arrangement
such that each player plays each day exactly once, and at the end,
each player plays with all the others. While I don't know the general way
to efficiently produce all such solutions, this code seems to get some
particular one in about a second or less on the average on my PC. It is
rather ad hoc in the way it looks for a solution - perhaps there are faster
and more systematic and elegant ways but I did not figure them out.
In[1] =
getSolution[numOfPlayers_?EvenQ] :=
Module[{pairs, incompatible, pickRandom, dayGames, result},
pairs = Select[Tuples[Range[numOfPlayers], 2], Less @@ # &];
incompatible =
Sort /@ Flatten[Thread[{#, Range[numOfPlayers]}] & /@ #, 1] &;
pickRandom = If[Length[#] == 0, Throw[$Failed], RandomChoice[#]] &;
dayGames[pairs_] :=
Reap[Nest[Complement[#,
incompatible@Sow@pickRandom[#]] &, pairs, numOfPlayers/2]][[2, 1]];
While[(result = Catch@Reap@Nest[Complement[#,
Sow@dayGames[#]]&, pairs, numOfPlayers - 1]) === $Failed];
Sort[Sort /@ result[[2, 1]]]];
In[2] = getSolution[10] // Timing
Out[2] =
{0.29,
{{{1,2},{3,6},{4,10},{5,7},{8,9}},
{{1,3},{2,9},{4,5},{6,10},{7,8}},
{{1,4},{2,6},{3,10},{5,8},{7,9}},
{{1,5},{2,10},{3,9},{4,7},{6,8}},
{{1,6},{2,5},{3,8},{4,9},{7,10}},
{{1,7},{2,3},{4,8},{5,10},{6,9}},
{{1,8},{2,7},{3,4},{5,6},{9,10}},
{{1,9},{2,4},{3,5},{6,7},{8,10}},
{{1,10},{2,8},{3,7},{4,6},{5,9}}}}
For larger number of players it admittedly takes longer and longer
to get a result. What I also don't know is whether or not all different
solutions are only different up to relabeling the players, or there are
some "topologically nonequivalent" ones.
Regards,
Leonid
On Fri, May 1, 2009 at 2:24 AM, Dr. Bruno Campanini <cmpbrn at 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?
>
> I do know how to get the matrix with a simple Visual Basic routine
> (some 30 lines of code).
> I was wondering if there is a shorter Mathematica simple formula
> for the same job.
>
> Bruno
>
>