t-sql - 组合学

Question

我正在尝试在可变长度字符串中找到所有可能的字符组合。

例如：“--”将有 2^n = 2^2 = 4 种可能性，“x-”、“-x”、“xx”、“--”

我认为基本上我需要循环 c(2,2) + c(2,1) + c(2,0) 其中 c(n,r) = n！/ (r! * (nr)!) 但是我在使用 cte 处理事情时遇到了麻烦。到目前为止，随着您向字符串添加字符，一切都开始崩溃了。

使用数字表 -

declare @s varchar(15)
set @s = '--'

;with subset as (
select cast(stuff(@s,number,1,'x') as varchar(15)) as token,
     cast('.' + cast(number as char(1)) + '.' as varchar(11)) as permutation,
     cast(1 as int) as iteration ,
     number
from numbers where number between 1 and len(@s)
union 
select @s, '.0.', 1, 0
) ,

combination as (
select  cast(stuff(token,n.number,1,'x') as varchar(15)) as token ,
    CAST(permutation+CAST(n.number AS CHAR(1))+'.' AS VARCHAR(11)) AS permutation,
    iteration + 1 as iteration,
    n.number   
from subset s   inner join numbers n on substring(s.permutation,2,1) = n.number + 1
where n.number between 1 and len(@s)
)

select * from subset union combinations

这返回

token           permutation iteration   number
--------------- ----------- ----------- -----------
--              .0.         1           0
x-              .1.         1           1
-x              .2.         1           2
xx              .2.1.       2           1

我不知道如何让它工作超过两个字符（'---'、'----' ...）也许我正在看这个错误的任何指针将不胜感激。对不起，我知道 sql 很丑，有很多错误。即使经过几天的研究，我对 cte 的了解也是可怕的。

Answer 1

假设您有一个包含整数的辅助 Numbers 表。

DECLARE @s VARCHAR(5);
SET @s = 'ABCDE';

WITH Subsets AS (
SELECT CAST(SUBSTRING(@s, Number, 1) AS VARCHAR(5)) AS Token,
CAST('.'+CAST(Number AS CHAR(1))+'.' AS VARCHAR(11)) AS Permutation,
CAST(1 AS INT) AS Iteration
FROM dbo.Numbers WHERE Number BETWEEN 1 AND 5
UNION ALL
SELECT CAST(Token+SUBSTRING(@s, Number, 1) AS VARCHAR(5)) AS Token,
CAST(Permutation+CAST(Number AS CHAR(1))+'.' AS VARCHAR(11)) AS
Permutation,
s.Iteration + 1 AS Iteration
FROM Subsets s JOIN dbo.Numbers n ON s.Permutation NOT LIKE
'%.'+CAST(Number AS CHAR(1))+'.%' AND s.Iteration < 5 AND Number
BETWEEN 1 AND 5
--AND s.Iteration = (SELECT MAX(Iteration) FROM Subsets)
)
SELECT * FROM Subsets
WHERE Iteration = 5
ORDER BY Permutation

Token Permutation Iteration
----- ----------- -----------
ABCDE .1.2.3.4.5. 5
ABCED .1.2.3.5.4. 5
ABDCE .1.2.4.3.5. 5
(snip)
EDBCA .5.4.2.3.1. 5
EDCAB .5.4.3.1.2. 5
EDCBA .5.4.3.2.1. 5