# Thinking outside the box

Patron Saint of Lost Yaks

## Create permutations, a simple way

This is one way to create permutations of a word. It is certainly not the fastest way (there are hardwired and specialized approaches, and there are other algorithms such as Fike) but this is very simple.

DECLARE @Word VARCHAR(10) = 'Peter'

;WITH cteYak(Word, Letters)
AS (
SELECT  CAST(SUBSTRING(@Word, Number, 1) AS VARCHAR(10)) AS Word,
STUFF(@Word, Number, 1, '') AS Letters
FROM    dbo.TallyNumbers
WHERE   Number BETWEEN 1 AND LEN(@Word)

UNION ALL

SELECT      CAST(Word + SUBSTRING(y.Letters, n.Number, 1) AS VARCHAR(10)) AS Word,
STUFF(y.Letters, n.Number, 1, '') AS Letters
FROM        cteYak AS y
INNER JOIN  dbo.TallyNumbers AS n ON n.Number BETWEEN 1 AND LEN(y.Letters)
)
SELECT  DISTINCT
Word
FROM    cteYak
WHERE   LEN(Word) = LEN(@Word)

Print | posted on Saturday, January 02, 2010 8:15 AM | Filed Under [ SQL Server 2008 Algorithms SQL Server 2005 ]

## #re: Create permutations, a simple way

Hi Peso

Here's an alternative approach. It uses powers of 2 together with the bitwise AND operator (&).

DECLARE @Word VARCHAR(MAX); SET @Word = 'RyanR';

; WITH
Letters (Letter, Marker) AS(
SELECT SUBSTRING(@Word, Number, 1), POWER(2, Number-1) --power of 2 marker
FROM dbo.TallyNumbers WHERE Number BETWEEN 1 AND LEN(@Word) AND Number < 1000) --surprising error without this last clause
, Words (Marker, Level, Word) AS (
SELECT Marker, 1, CAST(Letter AS VARCHAR(MAX)) FROM Letters
UNION ALL
SELECT a.Marker + b.Marker, b.Level + 1, b.Word + a.Letter
FROM Letters a INNER JOIN Words b ON a.Marker & b.Marker = 0
WHERE b.Level < LEN(@Word))
SELECT DISTINCT Word FROM Words WHERE level = LEN(@Word) ORDER BY Word

1/7/2010 4:19 PM | Ryan Randall

## #re: Create permutations, a simple way

It is not that surprisingly. It's because @Word is declared as VARCHAR(MAX), so the optimizer has to account for 2 GB text in worse case, and then POWER(2, number) will be far out of scope.
Change VARCHAR(MAX) to VARHAR(20) and remove the "AND Number < 1000" and it will work!
1/7/2010 4:27 PM | Peso

## #re: Create permutations, a simple way

If you keep @Word as VARCHAR(MAX), the largest number for &quot;AND Number &lt; &quot; is 30136. For 30137 you get same error as before, "INTEGER out of bounds".
1/7/2010 4:33 PM | Peso

## #re: Create permutations, a simple way

The issue I'm seeing isn't as simple as the one you're describing a solution to.

> Change VARCHAR(MAX) to VARHAR(20) and remove the "AND Number < 1000" and it will work!
No, this doesn't work (on my machine).

Regardless of the VARCHAR size...

Using "FROM dbo.TallyNumbers WHERE Number BETWEEN 1 AND LEN(@Word)" fails with the error "Arithmetic overflow error for type int, value = 2147483648.000000." (on my machine).

Using "FROM dbo.TallyNumbers WHERE Number BETWEEN 1 AND 5" works fine (on my machine).

I find that surprising.
1/7/2010 5:03 PM | Ryan Randall

## #re: Create permutations, a simple way

I've now changed it to VARHAR(20). It was laziness on my part not to do that before. I still haven't figured out how to avoid the extra clause, however.

For me, this runs in about 30ms, and is roughly twice as quick as using VARCHAR(MAX). Your suggestion runs in about 5s for me (I acknowledge you weren't aiming for speed).

DECLARE @Word VARCHAR(20); SET @Word = 'RyanR';

; WITH
Letters (Letter, Marker) AS(
SELECT SUBSTRING(@Word, Number, 1), POWER(2, Number-1)
FROM dbo.TallyNumbers WHERE Number BETWEEN 1 AND LEN(@Word) AND Number <= 20)
, Words (Marker, Level, Word) AS (
SELECT Marker, 1, CAST(Letter AS VARCHAR(20)) FROM Letters
UNION ALL
SELECT a.Marker + b.Marker, b.Level + 1, CAST(b.Word + a.Letter AS VARCHAR(20))
FROM Letters a INNER JOIN Words b ON a.Marker & b.Marker = 0
WHERE b.Level < LEN(@Word))
SELECT DISTINCT Word FROM Words WHERE level = LEN(@Word) ORDER BY Word
1/7/2010 5:36 PM | Ryan Randall

## #re: Create permutations, a simple way

I have tested both suggestions on my laptop with SQL Server 2008 R2 x64, and they run equally fast with up to 6 letters in the word. When there are 7 or 8 letters, my suggestion run 1 second faster (4.2 vs 5.2).
1/7/2010 10:25 PM |

## #re: Create permutations, a simple way

Interesting. I did some playing around in light of the huge difference between our tests on your code, and I've found that if I add "AND Number <= 10" to your code in 2 places, I get similar timings to you (SQL Server 2005).

It seems to me that on my box it's doing the calculations before evaluating "LEN(@Word)", and adding in the extra clause makes it evaluate only 1-10 rather than every row in the TallyNumbers table.

Incidentally, how big is your TallyNumbers table? Mine's 1,000,000 rows.

DECLARE @Word VARCHAR(10); SET @Word = 'PeterABC'

;WITH cteYak(Word, Letters)
AS (
SELECT CAST(SUBSTRING(@Word, Number, 1) AS VARCHAR(10)) AS Word,
STUFF(@Word, Number, 1, '') AS Letters
FROM dbo.TallyNumbers
WHERE Number BETWEEN 1 AND LEN(@Word) AND Number <= 10

UNION ALL

SELECT CAST(Word + SUBSTRING(y.Letters, n.Number, 1) AS VARCHAR(10)) AS Word,
STUFF(y.Letters, n.Number, 1, '') AS Letters
FROM cteYak AS y
INNER JOIN dbo.TallyNumbers AS n ON n.Number BETWEEN 1 AND LEN(y.Letters) AND Number <= 10
)
SELECT DISTINCT
Word
FROM cteYak
WHERE LEN(Word) = LEN(@Word)
1/8/2010 11:32 AM | Ryan Randall

## #re: Create permutations, a simple way

I have 100,000 records.
1/8/2010 11:49 AM | Peso

## #re: Create permutations, a simple way

I have 100,000 records, ranging from 0 to 999,999.
1/8/2010 11:50 AM |

## #re: Create permutations, a simple way

You mean 99,999?
1/8/2010 11:53 AM | Ryan Randall

## #re: Create permutations, a simple way

Yes. 0 to 99,999.
1/8/2010 12:01 PM |
Comments have been closed on this topic.