Ecky wrote:It actually isn't that hard at all if you have some basic maths/programming skills. I've seriously thought about approaching the SANFL and offering to put together the draw for them, as each year they put together a draw with many confusing features that are clearly not optimal, as discussed here...
All you would need is for the SANFL to give
1) A list of features the draw must have (like foxtel cup constraints etc..., number of rounds in a season etc.)
2) A wish list of additional features that would be preferable to have (like teams have at least 6 weeks between byes or whatever...)
You could then easily write a program that has the first list set in stone, and then cycle through the many (maybe millions?) of permutations of possible draws and rank them all depending on how many of the wish list features are satisfied. (This would probably only take a few hours to run).
Then you could give the SANFL the top 5 or so sample draws, and they could pick the one they like the best (in consultation with the clubs)
It isn't rocket science and there are people who would do it for free...
Good work Ecky
I have already given thought to this myself. There are 945 ways any particular round could be drawn in a ten-team competition (treating the bye as a team, and not distinguishing home from away teams). Any entire draw of N rounds can thus be expressed as a point in an N-dimensional vector space over a field of finite integers. The obvious algorithm is an exhaustive search over all 945^N points. This is clearly infeasible.
The search is simplified by introduction of a number of constraints (no two teams play in consecutive weeks, last year's grand finalists play on ANZAC weekend, etc). This partitions the vector space into regions of feasibility and infeasibility. The region of feasible solutions would be drastically less than the size of the space, but still very large - far too large to "cycle through all possible combinations".
A depth-first search of the vector space with severe heuristic direction and pruning
might provide a solution in reasonable time, as might a directed random search. I would seed a random search with a "first attempt" done by hand (i.e. what Booney suggests above, or maybe take the draw from a previous season), and progressively perturb this until a satisfactory draw was reached. Or I might simply pick up a text on Operations Research and apply integer programming algorithms to the task.
As a measure of goodness I would take the list of club (and SANFL) requests, weight each one by a factor of "desirability", and sum the weights of all requests satisfied by any candidate solution. The objective surface described by this measure would likely be highly multimodal, but this is actually in our favour; we need not search for the absolute best draw, just for one which is sufficiently good - meaning we might get away with looking at a fraction of the set of feasible draws before settling on one.
Give me sufficient time and money, and I'll do it....
