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)
Legacy Comments
|
Ryan Randall
2010-01-07 |
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 |
|
Peso
2010-01-07 |
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! |
|
Peso
2010-01-07 |
re: Create permutations, a simple way If you keep @Word as VARCHAR(MAX), the largest number for "AND Number < " is 30136. For 30137 you get same error as before, "INTEGER out of bounds". |
|
Ryan Randall
2010-01-07 |
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. |
|
Ryan Randall
2010-01-07 |
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 |
|
Peso
2010-01-07 |
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). |
|
Ryan Randall
2010-01-08 |
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) |
|
Peso
2010-01-08 |
re: Create permutations, a simple way I have 100,000 records. |
|
Peso
2010-01-08 |
re: Create permutations, a simple way I have 100,000 records, ranging from 0 to 999,999. |
|
Ryan Randall
2010-01-08 |
re: Create permutations, a simple way You mean 99,999? |
|
Peso
2010-01-08 |
re: Create permutations, a simple way Yes. 0 to 99,999. |