Jeff wrote the following in the comments section:
Thanks for this informative site. It's really helped me out a lot. Really great stuff.
Now for the complicated question...
I'm trying to create a tournament scheduling program that creates a schedule based on the number of players given, and a specified number of players per team. For example, the user could create a schedule for 12 players, with 3 players per team. Or for 16 payers, 2 to a team. The team size can vary from 1 to N, where N is (number of players) / 2.
What I'm looking for is an alogrithm to generate a tournament so that every player plays every other, AND so that every player plays *with* as many other players as possible. They may not play with all other players (After reading the page on "social squares" I realized this isn't always possible), but they should play against all others.
This problem's difficult because the team size can vary. Any ideas for how I can create varied teams? All my efforts so far create schedules where some players are frequently on the same team, and I'm wonderign how to reduce this. Anyplace I should look for input? What sort of algorithm should I be looking at?
Thanks again for the great site.
My reply follows below
Jeff,
Some suggestions for a basic algorithm:
Start with a random assignments of the N players to the teams in each round, make a table that counts the number of times players play against each other and another table counting the number of times players play with each other. Make the best improvement to the schedule possible by swapping two players between teams in the same round. Here the word “improvement” needs to be translated into some objective function that you would use to seek the best eveness of the counts in the two tables. Update the two tables and keep going until no further improvement is possible.
Having said that, don't ignore what combinatorics can offer. For example the following cyclic schedule,
(124) v (356) (0)
(235) v (460) (1)
(346) v (501) (2)
(450) v (612) (3)
(561) v (023) (4)
(602) v (134) (5)
(013) v (245) (6)with 7 players, 2 teams of 3 and one bye per round, has very nice properties; all partners twice (once of the left once on the right) and all opponents three times. It's from Lamken,E.R. (1990) “Generalized Balanced Tournament Designs”, Trans. Am. Math. Soc., vol 318, p473-490.
Regards,
Ian.
