Thinking outside the box

Patron Saint of Lost Yaks
posts - 203, comments - 734, trackbacks - 4

My Links

Advertisement

News

Archives

Post Categories

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 ]

Feedback

Gravatar

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

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

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

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

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

# 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 | Peso
Gravatar

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

# re: Create permutations, a simple way

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

# re: Create permutations, a simple way

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

# re: Create permutations, a simple way

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

# re: Create permutations, a simple way

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

Powered by:
Powered By Subtext Powered By ASP.NET