I'm trying to create a scheduler for a sports league and I'd like to schedule the teams in groups so every team gets one game per group. I think the thing I'm trying to do is an existing problem in computer science, but I don't know what it's called and I'm having trouble finding information about it. Either way, here's the situation:
Let's say I have a set of teams A = {1,2,3,...,n} and a set of pairs of those teams B = {(1,2), (1,3), (2,4), (6,9),...}. B does not have every possible combination of teams from A. Assume that A has an even number of teams. My program is trying to create a subset of B (lets call that subset S) such that every team from A appears in S exactly once. It does this by moving the pairs from B to S, one at a time. Let's say that it has already placed several pairs into S. How can I find out whether it is possible to successfully create S given the current situation?
Example:
A = {1,2,3,4}, B = {(1,2), (1,3), (1,4), (3,4)}
If after one move, S = {(1,2)}, then it can be completed by moving (3,4).
If after one move, S = {(1,3)}, then it cannot be completed.
Update: This algorithm will be one of the heuristics I use in my schedule generator. The goal is to implicitly split the schedule into "waves" where each team has one game per wave. So let's say that I have a pool of 16 teams and each team will have 5 games against other teams in the pool. An ideal schedule would make sure that no team has their second game before every team has had at least one game. The scheduler picks games one at a time and assigns them a date. So the idea is to have the scheduler keep track of the games scheduled in this "wave" and to never pick a game that would prevent each team from playing exactly once in the current wave. The scheduler also uses a bunch of other heuristics, so I can't explicitly order the games and have it go in order.
I'm sorry if this is unclear or not very rigorous. Feel free to ask for clarification and I'll do my best to explain further.
It's Maximum matching problem in graph theory. There are some known algorithms to solve it.
In your problem graph G (V - set of vertexes, E - set of edges) where V = A, E = B. Also add opposite edges to graph. Weight of each edge is 1.
I suggest you to use Hungarian Algorithm for bipartite graphs and Edmond's algorithm for others.