I have a table (players) containing a list of players, I would like to pair up these players in a unique way, so that every player's opponent is unique every round (ie. every time the SELECT query is called).
The player_opponent_log
column is an integer[]
which contains the player_id
s of players who have played with that player in a previous round (and is used to help pick out unique players). This column is populated afterwards using the results of the SELECT query – and is outside the scope of this question.
The table for instance would have the following data;
player_id | player_opponent_log
-----------+---------------------
1 | {2,3}
2 | {1}
3 | {1}
4 | {}
5 | {}
6 | {}
7 | {8}
8 | {7}
What I am trying to achieve would be something along the following lines:
player_id1 | player_id2
------------+------------
1 | 4
2 | 3
5 | 7
6 | 8
I have tried countless different approaches, including GROUP BY
, DISTINCT ON ()
, self JOINS, but haven't been able to come to a working solution.
The following result is what I am currently getting and am trying to avoid:
player_id1 | player_id2
------------+------------
1 | 4
2 | 3
3 | 4
4 | 1
5 | 1
6 | 1
7 | 1
8 | 1
Where I'm getting stuck is how to eliminate a single player being allocated for a round more than once per SELECT query.
Any ideas on how to solve this would be highly appreciated.
Best Answer
Every row of the result depends on the previous row. A
recursive CTEcomes to mind, I tried that. But one would need to refer to the worktable in anOUTER JOIN
or a subquery expression which is not allowed. This does not work (building on the table layout in my fiddle):I don't think there is a halfway decent way to solve this with pure SQL. I suggest:
Procedural solution with PL/pgSQL
How?
Build a temporary table with remaining possible pairs. This kind of cross join produces a lot of rows with big tables, but since we seem to be talking about tournaments, numbers should be reasonably low.
Players with the longest list of opponents are sorted first. This way, players that would be hard to match come first, increasing the chance for a solution.
Pick the first row and delete related pairings now obsolete. Do need to sort again. Logically any row is good, practically we get the player with the longest list of opponents first due to initial sort (which is not reliable without
ORDER BY
, but good enough for the case).Repeat until no match is left.
Keep count and raise an exception if the count is not as expected. PL/pgSQL conveniently allows to raise an exception after the fact, which cancels any previous return values. Details in the manual.
Call:
Result:
SQL Fiddle.
Note
This does not guarantee to calculate the perfect solution. I just returns a possible solution and uses some limited smarts to improve the chances to find one. The problem is a bit like solving a Sudoku, really and is not trivially solved perfectly.