Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Sep 20 '12 at 23:15

This question came from our site for professional and enthusiast programmers.

    
You might want to look into maximum matching. –  svick Nov 3 '11 at 19:28

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
I prefer Swiss, which gives middle rankings unlike double/single elimination, and finds the top N players in the same number of rounds as a N-elimination tournament. –  Mooing Duck Nov 3 '11 at 21:05

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.