Início / dba / Perguntas / 61173
Accepted
AbuAbdoh
Asked: 2014-03-19 09:38:24 +0800 CST

Pares únicos de autojunção

  • 772

Eu tenho uma mesa (jogadores) contendo uma lista de jogadores, gostaria de emparelhar esses jogadores de uma maneira única, para que o oponente de cada jogador seja único a cada rodada (ou seja, toda vez que a consulta SELECT for chamada).

A player_opponent_logcoluna integer[]contém os player_ids dos jogadores que jogaram com aquele jogador em uma rodada anterior (e é usada para ajudar a escolher jogadores únicos). Esta coluna é preenchida posteriormente usando os resultados da consulta SELECT - e está fora do escopo desta questão.

A tabela por exemplo teria os seguintes dados;

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

O que estou tentando alcançar seria algo ao longo das seguintes linhas:

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

Eu tentei inúmeras abordagens diferentes, incluindo GROUP BY, DISTINCT ON (), self JOINS, mas não consegui chegar a uma solução funcional.

O seguinte resultado é o que estou obtendo atualmente e estou tentando evitar:

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

Onde estou ficando preso é como eliminar um único jogador sendo alocado para uma rodada mais de uma vez por consulta SELECT.

Qualquer ideia sobre como resolver isso seria muito apreciada.

postgresql join

1 respostas

  1. Best Answer

    Cada linha do resultado depende da linha anterior. Um CTE recursivo vem à mente, eu tentei isso. Mas seria necessário referir-se à tabela de trabalho em uma OUTER JOINou uma expressão de subconsulta que não é permitida. Isso não funciona (com base no layout da tabela no meu violino ):

    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

    Não acho que haja uma maneira meio decente de resolver isso com SQL puro. Eu sugiro:

    Solução processual com 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;

    Como?

    Construa uma tabela temporária com os pares possíveis restantes. Esse tipo de junção cruzada produz muitas linhas com mesas grandes, mas como parece que estamos falando de torneios, os números devem ser razoavelmente baixos.

    Os jogadores com a lista mais longa de oponentes são classificados primeiro. Dessa forma, os jogadores que seriam difíceis de igualar vêm primeiro, aumentando a chance de uma solução.

    Escolha a primeira linha e exclua os pares relacionados agora obsoletos. Precisa classificar novamente. Logicamente qualquer linha é boa, praticamente pegamos o jogador com a lista mais longa de oponentes primeiro devido à classificação inicial (que não é confiável sem ORDER BY, mas boa o suficiente para o caso).

    Repita até não sobrar nenhuma correspondência.
    Mantenha a contagem e gere uma exceção se a contagem não for a esperada. O PL/pgSQL permite convenientemente lançar uma exceção após o fato, que cancela qualquer valor de retorno anterior. Detalhes no manual.

    Ligar:

    SELECT * FROM f_next_round();

    Resultado:

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

    SQL Fiddle.

    Observação

    Isso não garante o cálculo da solução perfeita. Eu apenas devolvo uma solução possível e uso alguma inteligência limitada para melhorar as chances de encontrar uma. O problema é um pouco como resolver um Sudoku , realmente e não trivialmente resolvido perfeitamente .

    • 1

relate perguntas