C# Algorithm to assign matches between teams in a sport

Possible Dup: Help Me Figure Out A Random Scheduling Algorithm using Python and PostgreSQL

Let's say you have a division with 9 teams, and you want them to play 16 games each. Usually you would want to have 8 games (Home), and 8 games (Visitor). Is there a known algorithm to go in and assign the matches, randomly?

Note -> It can, sometime开发者_运维知识库s not work, so you can have uneven numbers. Any help is appreciated.

See these permutation algorithms

Does this one work for you : Fisher–Yates shuffle

There's a nice easy way to generate a round robin here. In the second round, you can repeat the round-robin and add swap home and away.

If you have an odd number of teams, you just use a dummy team that gives its opponent a bye in a particular round, which results in an extra round. You can distribute that extra round among the other rounds if you'd rather give double-headers than byes.

I think you can use the maximal matching in a bipartite graph algorithm for this (see, e.g., here), which runs in polynomial time.

We represent your problem by assigning each team, T, 8 vertices (Th1, ..., Th8) in the "home" subset of vertices and 8 vertices (Ta1, ..., Ta8) in the "away" subset of the vertices.

We now look for a maximal matching between the "home" and "away" subsets such that each edge (H, A) in the matching satisfies the property that H is in the "home" subset, "A" is in the "away" subset, and H and A belong to different teams.