自加入唯一對

我有一個包含玩家列表的表（玩家），我想以獨特的方式將這些玩家配對，以便每個玩家的對手每輪都是唯一的（即每次呼叫 SELECT 查詢時）。

該player_opponent_log列是一個integer[]包含player_id在前一輪中與該玩家一起玩過的玩家的 s （用於幫助挑選獨特的玩家）。之後使用 SELECT 查詢的結果填充此列 - 並且超出了此問題的範圍。

例如，該表將具有以下數據；

player_id | player_opponent_log 
-----------+---------------------
        1 | {2,3}
        2 | {1}
        3 | {1}
        4 | {}
        5 | {}
        6 | {}
        7 | {8}
        8 | {7}

我想要實現的目標是：

player_id1 | player_id2 
------------+------------
         1 |          4
         2 |          3
         5 |          7
         6 |          8

我嘗試了無數不同的方法，包括GROUP BY, DISTINCT ON (), self JOINS，但一直未能找到可行的解決方案。

以下結果是我目前得到並試圖避免的結果：

player_id1 | player_id2 
------------+------------
         1 |          4
         2 |          3
         3 |          4
         4 |          1
         5 |          1
         6 |          1
         7 |          1
         8 |          1

我陷入困境的地方是如何消除每個 SELECT 查詢不止一次為一輪分配的單個玩家。

任何關於如何解決這個問題的想法都將受到高度讚賞。

結果的每一行都取決於前一行。我想到了遞歸 CTE ，我試過了。但是需要在OUTER JOIN不允許的子查詢表達式或子查詢表達式中引用工作表。這不起作用（**基於我小提琴中的表格佈局）：

WITH RECURSIVE
  t0 AS (SELECT *, COALESCE(array_length(opp_log,1), 0) AS len FROM tbl)
,  t1 AS (
  SELECT t1.player_id AS pl, t2.player_id AS p2
        ,t1.len AS len1, t2.len AS len2
  FROM   t0 t1, t0 t2 
  WHERE  t2.player_id <> t1.player_id
  AND    t2.player_id <> ALL (t1.opp_log)
  )
, cte AS (
  (
  SELECT pl, p2
  FROM   t1
  ORDER  BY len1 DESC, len2 DESC
  LIMIT  1
  )

  UNION ALL
  (
  SELECT pl, p2
  FROM   t1
  LEFT   JOIN cte c ON t1.p1 IN (c.p1, c.p2)
                       OR t1.p2 IN (c.p1, c.p2)
  WHERE  c.p1 IS NULL
  ORDER  BY len1 DESC, len2 DESC
  LIMIT  1
  )
  )
SELECT *
FROM   cte;

> ERROR:  recursive reference to query "cte" must not appear within an outer join

我認為用純 SQL 解決這個問題沒有半途而廢的方法。我建議：

使用 PL/pgSQL 的程序解決方案

CREATE OR REPLACE FUNCTION f_next_round()
 RETURNS TABLE (player_id1 int, player_id2 int) AS
$func$
DECLARE
  rows int := (SELECT count(*)/2 FROM tbl);  -- expected number of resulting rows
  ct   int := 0;                             -- running count
BEGIN

CREATE TEMP TABLE t ON COMMIT DROP AS         -- possible combinations
SELECT t1.player_id AS p1, t2.player_id AS p2
    , COALESCE(array_length(t1.opp_log,1), 0) AS len1
    , COALESCE(array_length(t2.opp_log,1), 0) AS len2
FROM   tbl t1, tbl t2 
WHERE  t2.player_id <> t1.player_id
AND    t2.player_id <> ALL (t1.opp_log)
AND    t1.player_id <> ALL (t2.opp_log)
ORDER  BY len1 DESC, len2 DESC;               -- opportune sort order

LOOP
  SELECT INTO player_id1, player_id2  p1, p2 FROM t LIMIT 1;

  EXIT WHEN NOT FOUND;
  RETURN NEXT;
  ct := ct + 1;                              -- running count

  DELETE FROM t                              -- remove obsolete pairs
  WHERE  p1 IN (player_id1, player_id2) OR 
         p2 IN (player_id1, player_id2);
END LOOP;

IF ct < rows THEN
  RAISE EXCEPTION 'Could not find a solution';
ELSIF ct > rows THEN
  RAISE EXCEPTION 'Impossible result!';
END IF;

END
$func$  LANGUAGE plpgsql VOLATILE;

如何？

用剩餘的可能對建構一個臨時表。這種交叉連接會產生很多帶有大表的行，但由於我們似乎在談論錦標賽，所以數字應該相當低。

擁有最長對手名單的玩家排在第一位。這樣一來，難以匹配的玩家優先，增加了解決的機會。

選擇第一行並刪除現在已過時的相關配對。確實需要重新排序。從邏輯上講，任何行都是好的，實際上，由於初始排序，我們首先得到對手列表最長的玩家（如果沒有 ，這是不可靠ORDER BY的，但對於這種情況來說已經足夠好了）。

重複直到沒有匹配。

如果計數不符合預期，請保持計數並引發異常。PL/pgSQL 方便地允許在事後引發異常，這會取消任何先前的返回值。手冊中的詳細資訊。

稱呼：

SELECT * FROM f_next_round();

結果：

player_id1 | player_id2
-----------+-----------
1          | 7
2          | 3
4          | 8
5          | 6

SQL小提琴。

筆記

這並不能保證計算出完美的解決方案。我只是返回一個可能的解決方案，並使用一些有限的智慧來提高找到一個的機會。這個問題有點像解決數獨問題，真的而且不是簡單的完美解決。

引用自：https://dba.stackexchange.com/questions/61173