Background and main question
I am studying algorithm analysis and design, and have been going through "Algorithm Design and Applications" by Goodrich and Tamassia.
One of the applications problems (A-11.2) poses the following:
Given a set, P, of n teams in some sport, a round-robin tournament is a collection of games in which each team plays each other team exactly once. Such round-robin tournaments are often used as the first round for establishing the order of teams (and their seedings) for later single- or double-elimination tournaments. Design an efficient algorithm for constructing a round-robin tournament for a set, P, of n teams assuming n is a power of 2.
The chapter is on the divide-and-conquer method, so I am assuming that they intend for us to use a recursive algorithm to solve the problem.
Approach
I assumed that every team would play in every round (i.e. there is no need for "bye weeks").
I tried to tackle this problem via two different approaches:
1) Place each team in a some sort of collection (or, assign each team an integer, and place those into a collection). Pop the head element from the collection, and make pairs with the elements remaining in the collection. Use these pairs to populate an n - 1 rounds * n - 2 matches grid, where n, as in the problem, is the number of teams. Repeat until one element is left in the collection.
This is not a "true" divide-and-conquer approach, and is O((n-1)!), I believe.
2) Use n - 1, n * n binary matrices to plot the matches for each round.
This approach is not divide-and-conquer at all. I know intuitively that it will work, but I'm not sure how I would implement it programmatically.
Conclusion
How can we solve this problem via the divide-and-conquer approach?
What kind of asymptotic behavior can we expect?
