[MS SQL] SQL 挑战 - 排列组合和阶层目录 (使用 CTE 递迴)

好久没有分享 SQL 题目让大家玩了，最近刚好遇到两个问题 排列组合 和 阶层目录，有兴趣的大大可以挑战看看。

题目1 - 排列组合

原始资料 甲乙丙丁戊，请展开原始资料的所有组合，并需符合下列两个条件。

结果不必排序，列出所有组合即可。

结果如下:

乙乙丁乙丁戊乙丙乙丙丁乙丙丁戊乙丙戊乙戊丁丁戊丙丙丁丙丁戊丙戊戊甲甲乙甲乙丁甲乙丁戊甲乙丙甲乙丙丁甲乙丙丁戊甲乙丙戊甲乙戊甲丁甲丁戊甲丙甲丙丁甲丙丁戊甲丙戊甲戊

原始资料语法

DECLARE @Data TABLE(    Id INT,    Txt NVARCHAR(10))INSERT INTO @Data VALUES     (1,N'甲'),    (2,N'乙'),    (3,N'丙'),    (4,N'丁'),    (5,N'戊')

题目2 - 阶层目录

原始资料是具有阶层性的目录，结构如下:

DECLARE @Data TABLE(    Id INT,    PatentId INT,    Txt NVARCHAR(1000))

原始资料如下:

最上层目录的 PatentId 为 0。

Id    PatentId     Txt----|----------|---------- 1  |    0     |   1 2  |    0     |   2 3  |    1     |   1-1 4  |    1     |   1-2 5  |    2     |   2-1 6  |    3     |   1-1-1

现在需要用 --> 串出该目录到 根目录 的所有阶层，结果如下:

Id    PatentId     Txt                R----|----------|----------|----------------------- 1  |    0     |   1         1         2  |    0     |   2         2 3  |    1     |   1-1       1 --> 1-1   4  |    1     |   1-2       1 --> 1-2   5  |    2     |   2-1       2 --> 2-1   6  |    3     |   1-1-1     1 --> 1-1 --> 1-1-1    

原始资料语法

DECLARE @Data TABLE(    Id INT,    PatentId INT,    Txt NVARCHAR(1000))INSERT INTO @Data VALUES    (1, 0, '1'),    (2, 0, '2'),    (3, 1, '1-1'),    (4, 1, '1-2'),    (5, 2, '2-1'),    (6, 3, '1-1-1')

解答1 - 排列组合

DECLARE @Data TABLE(    Id INT,    Txt NVARCHAR(10))INSERT INTO @Data VALUES     (1,N'甲'),    (2,N'乙'),    (3,N'丙'),    (4,N'丁'),    (5,N'戊')   ;WITH DLOOP (Id, Txt, R) AS (    SELECT Id, Txt, Txt AS R FROM @Data    UNION ALL    SELECT B.Id,            B.Txt,            CAST (A.R+B.Txt AS NVARCHAR(10)) AS R     FROM DLOOP AS A    INNER JOIN @Data AS B ON B.Id>A.Id)SELECT R FROM DLOOPORDER BY R

SQL

解答2 - 阶层目录

DECLARE @Data TABLE(    Id INT,    PatentId INT,    Txt NVARCHAR(1000))INSERT INTO @Data VALUES    (1, 0, '1'),    (2, 0, '2'),    (3, 1, '1-1'),    (4, 1, '1-2'),    (5, 2, '2-1'),    (6, 3, '1-1-1');WITH DLOOP AS(    SELECT Id, PatentId, Txt,           Txt AS R,            PatentId AS PrevId,           1 AS Dp    FROM @Data    UNION ALL    SELECT A.Id, A.PatentId, A.Txt,           CAST(B.Txt + ' --> ' + A.R AS NVARCHAR(1000)) AS R,       B.PatentId AS PrevId,       A.Dp + 1 AS Dp    FROM DLOOP AS A    INNER JOIN @Data AS B ON B.Id=A.PrevId), DResult AS (    SELECT Id, PatentId, Txt, R    FROM     (    SELECT *, ROW_NUMBER() OVER(PARTITION BY Id ORDER BY Dp DESC) AS G    FROM DLOOP    ) AS A    WHERE G=1)SELECT * FROM DResult

SQL

CTE 递迴

这两题都用到了 SQL 的 CTE 递迴，这边稍微简单介绍一下。

CTE 递迴结构

;WITH Recursive (    --初始资料    SELECT * FROM XXX    UNION ALL    --递迴查询    SELECT * FROM Recursive    INNER JOIN YYY )

递迴结构分为两个部分
上半部为初始资料的查询
下半部为递迴查询，中间透过 UNION ALL 连接
程式运行时会先执行初始查询的部分，这个部分只会进行一次
接着透过这些资料进行递迴查询
每次递迴会将上一次下半部的查询，当成下一次 CTE 的结果
而当下半部 查询为空 时结束递迴
这时会将之前每次递迴的结果 UNION ALL 并回传 (包含第一次上半部的结果)

执行过程蛮抽象的，不知道这样表达，大家懂不懂

第一题分析

第一题是个排列组合问题，观察结果后可以发现
每个项目的结果都是顺向的，例如不可能出现 乙甲
因此我以 甲乙丙丁戊 为基础
每次递迴时将每个项目 JOIN 小于自己编号的所有项目
最后在将所有结果加在一起就是答案

甲的递迴

 第一次递迴   第二次递迴   第三次递迴   第四次递迴-----------|-----------|-----------|-----------　　甲乙　　　　甲乙丙　　　甲乙丙丁　　 甲乙丙丁戊　　甲丙　　　　甲乙丁　　　甲乙丙戊　　甲丁　　　　甲乙戊　　　甲乙丁戊　　甲戊　　　　甲丙丁　　　甲丙丁戊　　　　　　　　甲丙戊　　　　　　　　甲丁戊

乙的递迴

 第一次递迴   第二次递迴   第三次递迴-----------|-----------|-----------　　乙丙　　　　乙丙丁　　　乙丙丁戊　　乙丁　　　　乙丙戊　　乙戊　　　　乙丁戊

程式说明

;WITH DLOOP (Id, Txt, R) AS (    -- 初始化资料 甲乙丙丁戊    SELECT Id, Txt, Txt AS R FROM @Data    UNION ALL    SELECT B.Id,  -- 每次回传最后一位的Id           B.Txt, -- 每次回传最后一位的Txt (其实不必这个栏位)           -- R为结果           -- A.R (上一次递迴的结果) + B.Txt (这次 Join 的项目)           CAST (A.R+B.Txt AS NVARCHAR(10)) AS R     FROM DLOOP AS A    -- Join 编号小于自己的项目    INNER JOIN @Data AS B ON B.Id>A.Id)

第二题分析

第二题如各位大大说的，是个标準的递迴题
逻辑很单纯每次透过 PatentId 找到上一层的目录
不过有一点要注意，因为在递迴过程会产生一些中间资料
因此最后要将这些资料过滤掉

例如以 1-1-1 这个目录来看

 第一次递迴     第二次递迴          第三次递迴-----------|---------------|---------------------   1-1-1     1-1 --> 1-1-1   1 --> 1-1 --> 1-1-1

最后结果会产生三笔资料，但其实我们只要最后一笔

1-1-11-1 --> 1-1-11 --> 1-1 --> 1-1-1  <-只需要这笔资料

因此在递迴中我新增了一个 Dp 栏位，纪录了目录的层数，最后就可以利用 Dp 找出最长的那笔资料。

程式说明

;WITH DLOOP AS(    -- 原始目录    SELECT Id, PatentId, Txt,           Txt AS R,            PatentId AS PrevId,           1 AS Dp   -- 设定第一层 Dp 为 1    FROM @Data    UNION ALL    SELECT A.Id, A.PatentId, A.Txt,   -- 原始目录的栏位           -- R为结果           -- B.Txt (为这次找到的上层目录) + A.R (上一次递迴的结果)           CAST(B.Txt + ' --> ' + A.R AS NVARCHAR(1000)) AS R,           -- PrevId 提供下一次递迴要去 Join 的 PatentId       B.PatentId AS PrevId,           -- 目录层数，最后用来找出最长的那个结果       A.Dp + 1 AS Dp    FROM DLOOP AS A    -- 利用 PatentId 找出上层目录     INNER JOIN @Data AS B ON B.Id=A.PrevId), DResult AS (    SELECT Id, PatentId, Txt, R    FROM     (        -- 利用原始目录 Id 进行分组，并以 Dp 排序    SELECT *, ROW_NUMBER() OVER(PARTITION BY Id ORDER BY Dp DESC) AS G    FROM DLOOP    ) AS A    WHERE G=1   -- 找出最多层的那笔资料)

结语

解答拖了好多天，今天才有空发文，不知道大家有没有玩的愉快。