| From: | |
| Date: | 22 Feb 2001 at 21:45:18 |
| Subject: | Re: League fixture generation. |
Hello Tim,
> I need an algorythmn to generate fixtures for a sporting league. All
> teams must play each other twice (home-away). The number of teams will
> always be even and >=20. All teams will play once on each occasion so
> the number of occasions would be (noOfTeams-1)*2.
So the result should be an n times n matrix where each cell tells on
which occasion the two teams (marked by row and column) should play.
E.g. if we denote the teams by letters and the occasions by numbers the
result for four teams would be:
A B C D
A � 1 2 3
B 4 � 3 2
C 5 6 � 1
D 6 5 4 �
I wonder if this assignment problem can be solved in polynomial time.
I tried a greedy approach which ran in expected O(n�) time, but for 20
teams it assigned them to 53 different occasions, where the optimal
should be only 38. For 40 teams the result was 109, rather than the
theoretical 78.
If you need an optimal solution (or just something better than my greedy
approach) then I wouldn't mind help you develop a metaheuristic which
could do better.
But I would imagine that your problem is a common problem, so it would
probably be wise to search the net first, as it may already be solved
by a dozen different people ;-)
> Sorry if this is a bit OT. I`ve given myself headaches trying to work
> it out and thought someone here might enjoy(?) the challenge.
I wonder if we should broaden the focus of this list?
Kind regards Allan
------------------------ Yahoo! Groups Sponsor ---------------------~-~>
eGroups is now Yahoo! Groups
Click here for more details
http://us.click.yahoo.com/kWP7PD/pYNCAA/4ihDAA/d8AVlB/TM
---------------------------------------------------------------------_->
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/