Thinking outside the box

# 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

# 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!

# 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".

# 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.

# 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

# 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).

# 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)

# re: Create permutations, a simple way

I have 100,000 records.

# re: Create permutations, a simple way

I have 100,000 records, ranging from 0 to 999,999.

# re: Create permutations, a simple way

You mean 99,999?

# re: Create permutations, a simple way

Yes. 0 to 99,999.