Swiss tournament - pairing algorithm

Question

I am working on a Swiss Tournament system in Python and I'm trying to figure out an optimal pairing algorithm.
My biggest problem is that every algorithm I came with produced error in few sequences, where the last pair to be picked have already played each other, ruling the pairing is invalid.

The Swiss system I'm working on is simple: even players, everyone plays at each round and pairing is done based on the winning proximity (so strong players play against strong players, and weak against weak).
No Bye, only win/lose (no draw), opponents cannot play each other twice.

The current algorithm I did works as follow:

1. Produce a players list by ranking order (most wins to least wins)
2. Pick player, starting from player with most wins
3. Match him with the closest ranked player. If they already played, match him with the next one, until a match is found
4. Pop the pair out of the list and back to 1

For example:
Ranking after 2 rounds:

1. P1: [P2 win, P3 win] 2 wins
2. P5: [P6 win, P2 win] 2 wins
3. P3: [P4 win, P1 lost] 1 win, 1 loss
4. P4: [P6 win, P3 lost] 1 win, 1 loss
5. P2: [P1 lost, P5 lost] 2 losses
6. P6: [P5 lost, P4 lost] 2 losses

First pick would be P1 and the first match is P5. Taking (P1,P5) out of the list.

1. P3: [P4 win, P1 lost] 1 win, 1 loss
2. P4: [P6 win, P3 lost] 1 win, 1 loss
3. P2: [P1 lost, P5 lost] 2 losses
4. P6: [P5 lost, P4 lost] 2 losses

First pick would be P3, already played P4, so the match would be P2. Taking (P3,P2) out of the list.
In this sequence I finish with a pair that played against each other and the pairing is invalid:

1. P4: [P6 win, P3 lost] 1 win, 1 loss
2. P6: [P5 lost, P4 lost] 2 losses

---

Question: Is there any algorithm that guarantees an optimal pairing module while making sure I do not get 'stuck' at the end with two players who played each other?

Answer 1

Maybe I could help you with that. In chess we have different Swiss pairing algorithms but they all work with a strong-weak pairing (there can be surprises).

The basic principle of the Dutch one (the most used) is that, once you have assigned your pairing numbers, you apply the algorithm for each score bracket.

The algorithm works roughly as follows:

In the first score bracket, pick (about) half the players and place them in a sub-group and place the other players in an other sub-group. If the players are compatible, then pair them together. If they are not compatible, try swapping players in the second sub-group. If no pairings are compatible, exchange players between subgroups. If there were an odd number of players in the bracket, one will float down.

In the next score bracket: If there are floaters, pair them first. Then, do the same thing as previously with residual group.

Some more rules are added to be sure that there IS at least one pairing possible.

For example : if no exchanges are able to make a good enough pairing, backtrack to the previous score bracket and break the pairing to make floaters.

This is a really rough explanation of the Dutch pairing system, but that was my go at your question.

Answer 2

A brute force algorithm would be guaranteed to find an optimal pairing module, if there is one:

1. Define penalty function for a pairing (probably the difference of wins of the paired players)
2. Based on this, define a penalty function for pairing modules (maybe the sum of squares of the respective penalty values of the pairings in the module)
3. Enumerate all valid modules (note that there might be none)
4. For each valid module, compute the module penalty value according to (2.)
5. Sort by this value and choose the (one of) module(s) with the smallest penalty value. (The minimum might be shared by several.)

For a small number of players, this might even result in feasible runtimes. For a larger number, you'd want to look into optimizations and shortcuts.