连接递归交叉连接

Question

我需要以递归交叉连接的方式连接名称。我不知道该怎么做，我已经尝试使用 WITH RECURSIVE 进行 CTE，但没有成功。

我有一个 table 这样的：

group_id | name
---------------
13       | A
13       | B
19       | C
19       | D
31       | E 
31       | F 
31       | G

期望的输出：

combinations
------------
ACE
ACF
ACG
ADE
ADF
ADG
BCE
BCF
BCG
BDE
BDF
BDG

当然，如果我添加第 4 个（或更多）组，结果应该成倍增加。

Answer 1

本机 Postgresql 语法：

SqlFiddleDemo

WITH RECURSIVE cte1 AS
(
  SELECT *, DENSE_RANK() OVER (ORDER BY group_id) AS rn
  FROM mytable
),cte2 AS
(
  SELECT 
    CAST(name AS VARCHAR(4000)) AS name,
    rn
  FROM cte1
  WHERE rn = 1
  UNION ALL
  SELECT
    CAST(CONCAT(c2.name,c1.name) AS VARCHAR(4000)) AS name
    ,c1.rn
  FROM cte1 c1
  JOIN cte2 c2
    ON c1.rn = c2.rn + 1
)
SELECT name as combinations
FROM cte2
WHERE LENGTH(name) = (SELECT MAX(rn) FROM cte1)
ORDER BY name;

之前:

我希望你不介意我使用 SQL 服务器语法：

样本：

CREATE TABLE #mytable(
   ID       INTEGER  NOT NULL
  ,TYPE     VARCHAR(MAX) NOT NULL
);
INSERT INTO #mytable(ID,TYPE) VALUES (13,'A');
INSERT INTO #mytable(ID,TYPE) VALUES (13,'B');
INSERT INTO #mytable(ID,TYPE) VALUES (19,'C');
INSERT INTO #mytable(ID,TYPE) VALUES (19,'D');
INSERT INTO #mytable(ID,TYPE) VALUES (31,'E');
INSERT INTO #mytable(ID,TYPE) VALUES (31,'F');
INSERT INTO #mytable(ID,TYPE) VALUES (31,'G');

主查询：

WITH cte1 AS
(
  SELECT *, rn = DENSE_RANK() OVER (ORDER BY ID)
  FROM #mytable
),cte2 AS
(
  SELECT 
    TYPE = CAST(TYPE AS VARCHAR(MAX)),
    rn
  FROM cte1
  WHERE rn = 1
  UNION ALL
  SELECT
    [Type]      = CAST(CONCAT(c2.TYPE,c1.TYPE) AS VARCHAR(MAX))
    ,c1.rn
  FROM cte1 c1
  JOIN cte2 c2
    ON c1.rn = c2.rn + 1
)
SELECT *
FROM cte2
WHERE LEN(Type) = (SELECT MAX(rn) FROM cte1)
ORDER BY Type;

LiveDemo

我假设 "cross join" 的顺序取决于 ID 的升序。

cte1 生成 DENSE_RANK() 因为您的 ID 包含空白
cte2 递归部分 CONCAT
主查询只是过滤掉所需的长度并对字符串进行排序

Answer 2

递归查询 在 Postgres 中更简单一些：

WITH RECURSIVE t AS (  -- to produce gapless group numbers
   SELECT dense_rank() OVER (ORDER BY group_id) AS grp, name
   FROM   tbl
   )
, cte AS (
   SELECT grp, name
   FROM   t
   WHERE  grp = 1

   UNION ALL
   SELECT t.grp, c.name || t.name
   FROM   cte c
   JOIN   t ON t.grp = c.grp + 1
   )
SELECT name AS combi
FROM   cte
WHERE  grp = (SELECT max(grp) FROM t)
ORDER  BY 1;

基本逻辑与中的相同，我添加了一些小改进。

或如果您的最大组数不太大，您可以使用简单版本(不能非常大，真的，因为结果集呈指数级增长）。最多 5 个组：

WITH t AS (  -- to produce gapless group numbers
   SELECT dense_rank() OVER (ORDER BY group_id) AS grp, name AS n
   FROM   tbl
   )
SELECT concat(t1.n, t2.n, t3.n, t4.n, t5.n) AS combi
FROM        (SELECT n FROM t WHERE grp = 1) t1
LEFT   JOIN (SELECT n FROM t WHERE grp = 2) t2 ON true
LEFT   JOIN (SELECT n FROM t WHERE grp = 3) t3 ON true
LEFT   JOIN (SELECT n FROM t WHERE grp = 4) t4 ON true
LEFT   JOIN (SELECT n FROM t WHERE grp = 5) t5 ON true
ORDER  BY 1;

少数小组的速度可能更快。 LEFT JOIN .. ON true 即使缺少更高级别，也能使这项工作正常进行。 concat() 忽略 NULL 值。使用 EXPLAIN ANALYZE 进行测试以确保。

SQL Fiddle 显示两者。

连接递归交叉连接

concatenate recursive cross join

sql

postgresql

combinatorics

recursive-query

common-table-expression