Sign up ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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 ,
from numbers where number between 1 and len(@s)
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,
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.

share|improve this question

migrated from Jan 25 '12 at 13:42

This question came from our site for professional and enthusiast programmers.

Sources of inspiration: 1, 2. – GSerg Jan 24 '12 at 23:04
What do you need this for? What you're generating just looks like a bit mask that's being incremented by 1: 000, 001, 010, 011, etc. – Nick Chammas Jan 25 '12 at 0:26
Why do you need to do this? And why are you tying to do it in SQL? – BalamBalam Jan 25 '12 at 2:23
I thought about a bit mask. Unfortunately our 3rd party db stores responses to questionnaires by character position in a string. 'x_x' would be a response of options 1 and 3. I used an auxillary number table and a function to pull the responses as a comma seperated string. Another option I pondered was pulling a table with every possible combination and looking up the responses based of a corresponding key. I'm probably wrong but it seems this might be faster. – sarov Jan 25 '12 at 4:05
So you want to convert a string of x---x into a list of numbers like 1 5 that corresponds to the positions of the xs. Is that correct? – Nick Chammas Jan 25 '12 at 19:11

3 Answers 3

up vote 1 down vote accepted

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)
    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)
        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'
        SET @i = @i + 1

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

    RETURN @bval


DECLARE @l int = 8
    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
share|improve this answer
It took me a second to wrap my head around this solution. I really like it. Clean and efficient. I ran it against a 14 character response string (16,384 combinations) and it ripped right through them before the key was up. – sarov Jan 26 '12 at 17:55
Yeah, it's just a simple decimal-to-binary converter, and a query that feeds the standard master..spt_values numbers table through it, then converts 1 and 0 to X and -. Of course, it only works for simple yes/no type questions. You'd have to make an arbitrary base converter to handle more than that. – db2 Jan 26 '12 at 21:09

Suppose you have a auxiliary Numbers table with integer numbers.

SET @s = 'ABCDE';

WITH Subsets AS (
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
SELECT CAST(Token+SUBSTRING(@s, Number, 1) AS VARCHAR(5)) AS Token,
CAST(Permutation+CAST(Number AS CHAR(1))+'.' AS VARCHAR(11)) AS
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
--AND s.Iteration = (SELECT MAX(Iteration) FROM Subsets)
WHERE Iteration = 5
ORDER BY Permutation

Token Permutation Iteration
----- ----------- -----------
share|improve this answer

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

select * from cte
share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.