T -SQL - Combinatoria

Question

Estoy tratando de encontrar todas las combinaciones de caracteres posibles en una cadena de longitud variable.

Por ejemplo: '-' tendría 2^n = 2^2 = 4 posibilidades, 'x-', '-x', 'xx', '-'

Creo que esencialmente necesito recorrer C (2,2) + C (2,1) + C (2,0) donde C (N, R) = N! / (¡R! * (NR)!) Pero tengo problemas para que las cosas funcionen con un CTE. Hasta ahora todo comienza a romperse con usted, agregue caracteres a la cadena.

Usando una tabla de números -

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

Esto regresa

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

No puedo entender cómo hacer que funcione más allá de dos personajes ('---', '----' ...) Tal vez estoy mirando esto mal, cualquier consejo sería muy apreciado. Perdón por el SQL, sé que es bastante feo con muchos errores. Incluso después de días de investigación, mi conocimiento de CTE es horrible.

Answer 1

Aquí hay un enfoque totalmente diferente que parece funcionar para este caso. Expandir y personalizarlo según sea necesario. Cambie el valor de @L para controlar el número de bits/preguntas en la salida.

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

Supongamos que tiene una tabla de números auxiliares con números enteros.

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

Me las arreglé para que funcionara la solución CTE. Hace un buen trabajo al proporcionar las combinaciones de personajes, pero se arrastra creando las cadenas de tokens. He incluido el código a continuación. La solución que DB2 proporcionó es el ganador. Crea las cadenas de tokens increíblemente rápidas y es bastante inteligente.

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