Question
I'm trying to find all possible character combinations in a variable length string.
For example: '--' would have 2^n = 2^2 = 4 possibilities, 'x-', '-x', 'xx', '--'
I think that essentially I need to loop through c(2,2) + c(2,1) + c(2,0) where c(n,r) = n! / (r! * (n-r)!) but I'm having trouble getting things to work in with a cte. So far everything starts to break down with you add characters to the string.
Using a numbers table -
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
This returns
token permutation iteration number
--------------- ----------- ----------- -----------
-- .0. 1 0
x- .1. 1 1
-x .2. 1 2
xx .2.1. 2 1
I can't figure out how to get it working past two characters ( '---', '----' ...) Maybe I'm looking at this wrong any pointers would be greatly appreciated. Sorry about the sql i know it's pretty ugly with lots of errors. Even after days of research my knowledge of cte's is horrid.
Solution
Here's a totally different approach that seems to work for this case. Expand and customize it as needed. Change the value of @l to control the number of bits/questions in the output.
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
OTHER TIPS
Suppose you have a auxiliary Numbers table with integer 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
I managed to get the cte solution working. It does a good job of providing the character combinations but crawls creating the token strings. I've included the code below. The solution that db2 provided is the winner. It creates the token strings incredibly fast and is pretty clever.
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