T -SQL - Kombinatorik

Question

Ich versuche, alle möglichen Zeichenkombinationen in einer Zeichenfolge mit variabler Länge zu finden.

Zum Beispiel: '-' hätte 2^n = 2^2 = 4 Möglichkeiten, 'x-', '-x', 'xx', '-' '

Ich denke, dass ich im Wesentlichen C (2,2) + C (2,1) + C (2,0) durchlaufen muss, wobei c (n, r) = n! / (r! * (nr)!) Aber ich habe Probleme, die Dinge mit einem CTE zusammenzuarbeiten. Bisher beginnt alles mit Ihnen zusammenzubrechen, was Charaktere zur Zeichenfolge hinzufügt.

Verwenden einer Zahlen Tabelle -

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

Dies kehrt zurück

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

Ich kann nicht herausfinden, wie ich es über zwei Charaktere arbeiten kann ('---', '----' ...). Vielleicht sehe ich das falsch an, was Zeiger sehr geschätzt werden. Tut mir leid wegen der SQL, ich weiß, dass es ziemlich hässlich ist, mit vielen Fehlern. Auch nach Tagen der Forschung ist mein Wissen über CTE schrecklich.

Answer 1

Hier ist ein völlig anderer Ansatz, der für diesen Fall zu funktionieren scheint. Erweitern und passen Sie es nach Bedarf an. Ändern Sie den Wert von @L, um die Anzahl der Bits/Fragen in der Ausgabe zu steuern.

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

Angenommen, Sie haben eine Hilfsnummernstable mit Ganzzahlzahlen.

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

Ich habe es geschafft, die CTE -Lösung zum Laufen zu bringen. Es leistet eine gute Arbeit, die Charakterkombinationen bereitzustellen, aber kriecht die Token -Saiten. Ich habe den Code unten aufgenommen. Die Lösung, die DB2 bereitstellte, ist der Gewinner. Es schafft die Token -Saiten unglaublich schnell und ist ziemlich klug.

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