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

我不知道如何使它在两个字符（'----'，'-----'...）上工作，也许我在看这个错误，任何指示都将不胜感激。对不起，我知道这很丑陋，有很多错误。即使经过几天的研究，我对CTE的了解也令人恐惧。

Answer 1

这是一种完全不同的方法，似乎对这种情况有用。根据需要进行扩展和自定义。更改@L的值以控制输出中的位/问题的数量。

CREATE FUNCTION dbo.bin_val(@val int, @trim bit)
RETURNS varchar(max)
AS
BEGIN
    DECLARE @hval varchar(256) = REPLACE(CONVERT(varchar, CAST(@val AS varbinary), 1), '0x', '')
    DECLARE @bval varchar(256) = ''
    DECLARE @i int = 1
    WHILE @i <= LEN(@hval)
    BEGIN
        SET @bval = @bval + CASE SUBSTRING(@hval, @i, 1)
                WHEN '0' THEN '0000'
                WHEN '1' THEN '0001'
                WHEN '2' THEN '0010'
                WHEN '3' THEN '0011'
                WHEN '4' THEN '0100'
                WHEN '5' THEN '0101'
                WHEN '6' THEN '0110'
                WHEN '7' THEN '0111'
                WHEN '8' THEN '1000'
                WHEN '9' THEN '1001'
                WHEN 'A' THEN '1010'
                WHEN 'B' THEN '1011'
                WHEN 'C' THEN '1100'
                WHEN 'D' THEN '1101'
                WHEN 'E' THEN '1110'
                WHEN 'F' THEN '1111'
            END
        SET @i = @i + 1
    END

    IF @trim = 1
        SET @bval = RIGHT(@bval, LEN(@bval) - ISNULL(NULLIF(CHARINDEX('1', @bval), 0), LEN(@bval)) + 1)

    RETURN @bval
END

GO

DECLARE @l int = 8
SELECT
    number,
    RIGHT(REPLACE(REPLACE(dbo.bin_val(number, 0), '1', 'X'), '0', '-'), @l)
FROM master..spt_values
WHERE type = 'P'
    AND number <= POWER(2, @l) - 1

Answer 2

假设您有一个带有整数编号的辅助数字表。

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

Answer 3

我设法使CTE解决方案正常工作。它在提供角色组合方面做得很好，但是爬行创建令牌字符串。我包括下面的代码。 DB2提供的解决方案是赢家。它可以快速创建令牌字符串，而且非常聪明。

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

with anchor as (
  select    n.number as id ,
            cast(stuff(@s,n.number,1,'x') as varchar(15)) as token ,
            cast('.' + cast(n.number as char(2)) + '.' as varchar(35)) as permutation 
  from numbers n
  where number between 1 and len(@s)
),
cte as (
  select    id as max_id ,
            cast(stuff(@s,id,1,'x') as varchar(15)) as token ,
            cast('.' + rtrim(cast(id as char(2))) + '.' as varchar(35)) as permutation ,
            cast(1 as int) as iteration
  from anchor 

  union all

  select    a.id as max_id ,
            cast(dbo.genresponse(c.permutation + cast(a.id as char(2)) + '.',len(@s)) as varchar(15)) as token ,
            a.token,
            cast(c.permutation +  cast(a.id as char(2)) + '.' as varchar(35)) as permutation,
            c.iteration + 1     
  from cte c
  inner join anchor a  on   a.id > c.max_id and c.permutation not like ('%.' + cast(a.id as varchar(35)) + '.%')
)

select * from cte