Is there a known algorithm for scheduling tournament matchups?

Question

Just wondering if there is a tournament scheduling algorithm already out there that I could use or even adapt slightly.

Here are my requirements:

• A variable number of opponents belonging to a variable number of teams/clubs each must be paired with an opponent
• Two opponents cannot be from the same club
• If there are an odd number of players, 1 of them randomly is selected to get a bye

Any algorithms related to this sort of requirement set would be appreciated.

EDIT: I only need to run this a maximum of one time, creating matchups for the first 'round' of the tournament.

Answer 1

As I can see you want to find maximum matching in graph. In fact nodes are players, they connected to each other if they aren't in same club, now you should find maximum number of edges which are doesn't have same vertex. See Edmonds Maximum matching algorithm.

Answer 2

From my brief time on Wikipedia twenty seconds ago it looks like you'll need to decide on an elimination strategy first. See Wikipedia:

1. Swiss-System
2. Single-elimination_tournament
3. Double-elimination_tournament

The single-elimination article described seeding techniques (the algorithm you're looking for) pretty generically and it looked helpful, although not quite an algorithm.

Answer 3

Making this up as I go, it seems like an initial matching algorithm is quite simple:

While two or more clubs have at least one member not paired  
    select the two clubs with the most unpaired members
    select a random unpaired member from each club
    pair those members

If one person is left, it will be a random person, with one exception. If one club has more members than all of the opposing players put together, then the leftovers will always be from that club. Realistically, that's a super-rare situation, and picking a buy from any other club would leave even more people leftover.