Generate all possible permutations of a given character set with a variable length in t-sql

Question

I have written the script below to generate all possible permutations of a specified set of characters.

Is there a way to efficiently do this while allowing the length to be specified at runtime?

DECLARE @string NVARCHAR(MAX)
SELECT @string = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

DECLARE @Chars TABLE (
    C CHAR(1) PRIMARY KEY
)

DECLARE @N INT 
SET @N = 1 
WHILE @N <= LEN(@string) BEGIN
    INSERT @Chars (
        C
    ) VALUES (
        SUBSTRING(@string, @N, 1)
    )

    SET @N = @N + 1
END

--SELECT * FROM @Chars


SELECT
    A.C + B.C + C.C
FROM @Chars A, @Chars B, @Chars C
ORDER BY
    A.C,
    B.C,
    C.C

Do you want to return the permutations as columns containing single characters? That would imply variable number of columns which would in turn imply dynamic scripting. Would a single column containing strings of specified length be all right instead? — Andriy M, Jul 18 '12 at 19:56
@AndriyM: Yes. And I edited my question to say that as well. Thank you. — Gabriel McAdams, Jul 18 '12 at 19:59
+1 for using a cartesian product to generate the permutations, very clever, but once you get to 10+ digits, that's going to really tax the database... — James L., Jul 18 '12 at 20:10
If the character set is always 36 characters, you can calculate the number of permutations and then create the permutations from 0 to n from base 10 to base 36, padding the left with zeros. I just did this the other day -- but for a given integer -- not a series of integers... It wasn't too hard approaching it from a base10 to a base36 conversion angle... (fixed comment, changed 26 to 36) — James L., Jul 18 '12 at 20:14
@JamesL.: The goal is to create a function with both the character set AND the length as parameters, allowing all printable characters. Perhaps limiting the length so as not to tax the database. — Gabriel McAdams, Jul 18 '12 at 20:15
36 characters @ 4 digits = 1.7Mil permutations; 5 digits = 60Mil; 6 digits = 2.2Bil; etc. What is your upper limit for both # of characters in the char set and the # of digits? — James L., Jul 18 '12 at 20:36

score 2 · Answer 1 · edited May 23 '17 at 11:56

If you are using SQL Server 2005 or later version, you could try a recursive CTE:

DECLARE @length int;
SET @length = 3;

WITH expanded AS (
  SELECT
    C = SUBSTRING(@string, N, 1)
  FROM numbers
  WHERE number BETWEEN 1 AND LEN(@string)
),
permutations AS (
  SELECT
    S = CAST(C AS nvarchar(max)),
    L = 1
  FROM expanded
  UNION ALL
  SELECT
    S = S + C,
    L = L + 1
  FROM permutations p
  CROSS JOIN expanded e
  WHERE L < @length
)
SELECT *
FROM permutations
WHERE L = @length
;

Here numbers is an auxiliary table of numbers, used to expand the string into a column of single characters.

Without more changes, this query would work with @length values up to 100 without issues. If you want permutations of greater length, you'll need to append this line:

OPTION (MAXRECURSION n)

where n is an integer value from 0 to 32767 indicating the maximum number of iterations of the recursive CTE, and the 100 mentioned above is the default. Nil actually means no limitation, which should probably be used with care.

You can try this query (and play with it) at SQL Fiddle, where I reduced the @string to just 8 characters (to be able to specify more different values for @length without making the query to return too many rows) and also defined the numbers table as a subset of a system table master..spt_values.

This solution does work, but I don't like that it generates all permutations with lengths at or below the specified length. As the specified length and/or the length of the character set grows.... this wont scale very well. — Gabriel McAdams, Jul 18 '12 at 21:15

score 0 · Accepted Answer · answered Jul 18 '12 at 21:40

After receiving comments related to the number of possible permutations, I realized that there should be very tight limits on the length of the character set as well as the specified length.

Given that the allowable length would be extremely small, I see no harm in using a condition in my script... like this:

DECLARE
    @string NVARCHAR(40), --limit the length of the character set to 40
    @length INT -- the limit for this is in a validation check below

SELECT
    @string = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ',
    @length = 2



IF (@length < 1 OR @length > 4) BEGIN
    RAISERROR('Invalid length specified. This function only supports lengths from 1 to 4', 16, 1)
END



DECLARE @Chars TABLE (
    C CHAR(1) PRIMARY KEY
)

;WITH numbers AS (
    SELECT TOP(LEN(@string)) number
    FROM master..spt_values
    WHERE type = 'P'
    AND number != 0
)

INSERT @Chars (
    C
)
SELECT
    C = SUBSTRING(@string, number, 1)
FROM numbers


IF (@length = 1) BEGIN
    SELECT C FROM @Chars ORDER BY C
END ELSE IF (@length = 2) BEGIN
    SELECT A.C + B.C
    FROM @Chars A, @Chars B
    ORDER BY A.C, B.C
END ELSE IF (@length = 3) BEGIN
    SELECT A.C + B.C + C.C
    FROM @Chars A, @Chars B, @Chars C
    ORDER BY A.C, B.C, C.C
END ELSE IF (@length = 4) BEGIN
    SELECT A.C + B.C + C.C + D.C
    FROM @Chars A, @Chars B, @Chars C, @Chars D
    ORDER BY A.C, B.C, C.C, D.C
END

Generate all possible permutations of a given character set with a variable length in t-sql

2 Answers2