Generating Permutations in T-SQL

Question

Post reply

Generating Permutations in T-SQL

Eli Leiba

SSC-Addicted

Points: 461
More actions
September 8, 2005 at 9:40 pm

#187577

Comments posted to this topic are about the content posted at http://www.sqlservercentral.com/columnists/eleiba/generatingpermutationsintsql.asp

Viewing 15 posts - 1 through 15 (of 15 total)

You must be logged in to reply to this topic. Login to reply

John Scarborough Ten Centuries Points: 1104 More actions · Answer 1

Nice article! I really had to "think" my way through this one, but its likely to be very useful.

John Scarborough
MCDBA, MCSA

HelloFOFO Old Hand Points: 349 More actions · Answer 2

I think it is better to limit the input parameter @n <= 10.

I modify this proc in my SQL 2000 Query Analyzer

just change the length of all parameters such as @sqlStmt,@base etc. to

5000

Then,I used 11 as input parameter and the Query Analyzer return an error:

can't generate query plan......

But I didn't try 10......

Michael Wang SSC Veteran Points: 203 More actions · Answer 3

I see nothing wrong with procedural code if implemeneted properly. The original code has the problem of being too complex and is also limited in scope. I ran it up to 7, beyond which my SQL2000 will not be able to generate a plan. The procedure below is inspired by the original code but is drastically different: it handles large set really fast and dynamic SQL statement is short and recursive (use @debug = 1 to see it).

To use it, you need to store your values in a table with a single column 'x'. This procedure permutes r out of n. Of course you need to make sure r<=n, and be aware that the result set could be substantial (n! / (n-r)! permutations).

It may not be useful, but just for fun.

Create Proc sp_permutate (@n smallint, @t varchar(8), @debug bit = 0)

as

begin

set nocount on

declare @sqlStmt varchar(4000), @delim varchar(2)

declare @i int

declare @j-2 int

if @debug = 1 set @delim = char(10) else set @delim = ''

set @sqlStmt = 'SELECT x' + cast(@n as varchar(2)) + '=X from ' + @t + @delim

set @i = @n -1

while @i > 0

Begin

set @j-2 = @n

set @sqlStmt = 'SELECT x' + cast(@i as varchar(2)) + '=X, T.* from ' + @t +

' join (' + @delim + @sqlStmt + ') T on x<>x' + cast(@j as varchar(2))

set @j-2 = @j-2 - 1

while @j-2 > @i

Begin

set @sqlStmt = @sqlStmt + ' and x<>x' + cast(@j as varchar(2))

set @j-2 = @j-2 - 1

End

set @sqlStmt = @sqlStmt + @delim

set @i = @i - 1

End

print @sqlStmt

exec (@sqlStmt)

set nocount off

end

go

Eli Leiba SSC-Addicted Points: 461 More actions · Answer 4

SQL 2005 has CTE that can do the permutations more easy

I coded for SQL-2000 ,

If you use a phisical table and not a "memory table" like

(select 1 union select 2 union ........)

then the optimizer will crush for more than 10 join with the table

to itself so memory derived tables must be used on this one

RyanRandall SSChampion Points: 13623 More actions · Answer 5

Hi all,

I wrote this for fun, and thought I'd share it here, since it's vaguely related. It's interesting mathematics (in that the method works) if nothing else.

If you set @i below to your set size, then a list of all combinations of numbers is returned (as a varchar). e.g. @i = 3 gives:

210

201

120

021

102

012

The timings on my pc are:

Size Seconds Rows

7 0 5040

8 1 40320

9 6 362880

10 60 3628800

--This SQL script is safe to run

--Inputs

DECLARE @i TINYINT

SET @i = 7 --set size

--Validation

IF @i > 10 BEGIN PRINT 'i is too large' SET @i = 0 END

--Declarations

CREATE TABLE #t (n TINYINT, v VARCHAR(10))

CREATE CLUSTERED INDEX #ix_t ON #t (n)

DECLARE @n TABLE (i TINYINT) --numbers table

DECLARE @Counter INT

--Initialisations

INSERT @n SELECT 0

INSERT #t SELECT 0, '0 '

SET @Counter = 1

--Loop for each integer from 1 to @i-1

WHILE @Counter <= @i - 1

BEGIN

INSERT @n SELECT @Counter

INSERT #t SELECT @Counter, STUFF(v, i+1, 0, @Counter)

FROM #t, @n WHERE n = @Counter - 1

SET @Counter = @Counter + 1

END

--Select results we're interested in

SELECT v FROM #t WHERE n = @i - 1

--Tidy up

DROP TABLE #t

Ryan Randall

Solutions are easy. Understanding the problem, now, that's the hard part.

Dennis D. Allen Say Hey Kid Points: 699 More actions · Answer 6

Just to toss my hat in the ring...

create procedure dbo.usp_permutate

@charset nvarchar(256) = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

as

set nocount on

-- a set of all values in the charset

create table #set ( k int, v nchar(1) )

declare @i int, @C nvarchar(5)

declare @select nvarchar(4000)

declare @from nvarchar(4000)

select

@i = 1

, @select = 's1.v '

, @from = '#set s1 '

insert into #set ( k, v ) values ( 1, substring(@charset, @i, 1) )

while @i < len(@charset) begin

set @i = @i + 1

set @C = convert(nvarchar(5), @i)

insert into #set ( k, v ) values ( 1, substring(@charset, @i, 1) )

set @select = @select + '+ s' + @C + '.v '

set @from = @from + 'join #set s' + @C + ' on s' + @C + '.k = s1.k '

end

-- output query

exec( 'select ' + @select + 'as permutation from ' + @from + 'order by permutation' )

-- clean up

drop table #set

Frédéric BROUARD Old Hand Points: 315 More actions · Answer 7

This calculus can be done in only one query

(I think I am the first to demontsrate how to do that in one query only !) 😉

-- lest's assume that this table containes all datas to be permuted :

CREATE TABLE T_CMB (CMB_DATA VARCHAR(8))

-- let's assume that the joker character ; (dot comma) is not used inside the data :

INSERT INTO T_CMB VALUES ('ABC')

INSERT INTO T_CMB VALUES ('DEF')

INSERT INTO T_CMB VALUES ('GHI')

-- the following query does the permutations

WITH

T_DATA AS

(SELECT CMB_DATA, 1 AS COMBINAISON,

ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE,

COUNT(*) OVER() AS N

FROM T_CMB),

T_RECUR AS

(SELECT CAST(CMB_DATA AS VARCHAR(max)) +';' AS CMB_DATA, COMBINAISON, ORDRE, N

FROM T_DATA

UNION ALL

SELECT T1.CMB_DATA + ';' + T2.CMB_DATA, T2.COMBINAISON + 1, ROW_NUMBER() OVER(PARTITION BY T1.COMBINAISON ORDER BY T2.CMB_DATA) ORDRE, T1.N

FROM T_DATA AS T1

CROSS JOIN T_RECUR AS T2

WHERE T2.COMBINAISON < T1.N

-- this line must be delete if you want a repetitive permutation

AND T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'

),

T_COMBINE AS

(SELECT CMB_DATA, ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE

FROM T_RECUR

WHERE COMBINAISON = N),

T_N AS

(SELECT 1 AS N

UNION ALL

SELECT N + 1

FROM T_N

WHERE N + 1 <= ALL (SELECT LEN(CMB_DATA)

FROM T_COMBINE)),

T_SOL AS

(SELECT *, REVERSE(SUBSTRING(CMB_DATA, 1, N-1)) AS SOUS_CHAINE,

REVERSE(SUBSTRING(REVERSE(SUBSTRING(CMB_DATA, 1, N-1)), 1,

CASE

WHEN CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1 = -1 THEN LEN(CMB_DATA)

ELSE CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1

END)) AS DATA

FROM T_COMBINE

INNER JOIN T_N

ON SUBSTRING(CMB_DATA, N, 1) = ';')

SELECT DATA AS CMB_DATA, ORDRE AS PERMUTATION

FROM T_SOL

CMB_DATA PERMUTATION

------------------------- --------------------

ABC 1

DEF 1

GHI 1

ABC 2

GHI 2

DEF 2

DEF 3

ABC 3

GHI 3

DEF 4

GHI 4

ABC 4

GHI 5

ABC 5

DEF 5

GHI 6

DEF 6

ABC 6

If you want a permutation with repetitive datas, simply delete the 18e line :

AND T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'

You'll get :

CMB_DATA PERMUTATION

----------------------- --------------------

ABC 1

ABC 2

DEF 2

ABC 3

GHI 3

ABC 4

DEF 4

ABC 4

ABC 5

DEF 5

ABC 6

DEF 6

GHI 6

ABC 7

GHI 7

ABC 7

ABC 8

GHI 8

DEF 8

ABC 9

GHI 9

DEF 10

ABC 10

DEF 11

ABC 11

DEF 11

DEF 12

ABC 12

GHI 12

DEF 13

ABC 13

DEF 14

DEF 15

GHI 15

DEF 16

GHI 16

ABC 16

DEF 17

GHI 17

DEF 17

DEF 18

GHI 18

GHI 19

ABC 19

GHI 20

ABC 20

DEF 20

GHI 21

ABC 21

GHI 21

GHI 22

DEF 22

ABC 22

GHI 23

DEF 23

GHI 24

DEF 24

GHI 24

GHI 25

ABC 25

GHI 26

DEF 26

GHI 27

The french version is on my blog :

http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathema

CU

---

Frédéric BROUARD, Spécialiste modélisation, bases de données, optimisation, langage SQL.

Le site sur le langage SQL et les S.G.B.D. relationnels : http://sqlpro.developpez.com/[/url]

Expert SQL Server http://www.sqlspot.com : audit, optimisation, tuning, formation

* * * * * Enseignant au CNAM PACA et à l'ISEN à Toulon * * * * *

RyanRandall SSChampion Points: 13623 More actions · Answer 8

Frédéric BROUARD (1/8/2009) ...

Here's something similar for comparison, making use of powers of 2 rather than LIKE, and XML rather than string manuipulation.

--preparation

IF OBJECT_ID('tempdb.dbo.#t1') IS NOT NULL DROP TABLE #t1

GO

--/

--structure

CREATE TABLE #t1 (x VARCHAR(MAX))

--/

--data

INSERT INTO #t1 VALUES ('ABC')

INSERT INTO #t1 VALUES ('DEF')

INSERT INTO #t1 VALUES ('GHI')

--/

--parameters

DECLARE @AllowDuplicates BIT

SET @AllowDuplicates = 0

--/

--query

; WITH

a AS (SELECT COUNT(*) AS cnt FROM #t1)

, b AS (SELECT POWER(2, ROW_NUMBER() OVER(ORDER BY x)-1) AS marker, x FROM #t1)

, c AS (SELECT marker, 1 as level, '<x>' + x + '</x>' AS x FROM b UNION ALL

SELECT c.marker + b.marker, c.level + 1, c.x + '<x>' + b.x + '</x>'

FROM b INNER JOIN c ON (@AllowDuplicates = 1 OR b.marker & c.marker = 0)

WHERE c.level < (SELECT cnt FROM a))

, d AS (SELECT ROW_NUMBER() OVER(ORDER BY x) as permutation, cast(x as xml) as xml

FROM c WHERE level = (SELECT cnt FROM a))

SELECT

d.permutation,

ROW_NUMBER() OVER(PARTITION BY d.permutation ORDER BY d.permutation) AS position,

c.value('.', 'varchar(100)') AS value

FROM d CROSS APPLY xml.nodes('//x') T(c)

--/

Ryan Randall

Solutions are easy. Understanding the problem, now, that's the hard part.

Frédéric BROUARD Old Hand Points: 315 More actions · Answer 9

Excellent.

I must say that I have try with power of 2 but I do not find a correct answer. But I do not like to use of XML wich is rather out of SQL control.

But your solution is quite more elegant.

I have had no time to tune my fisrt one. But I think there is a more concise way to do that job !

A + (wich me CU in french)

PS : I posted yourt solution, rewrited in my french blog !

http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathema

RyanRandall SSChampion Points: 13623 More actions · Answer 10

Thanks Frédéric 🙂

I dare say that's my first ever 'publication' in a foreign language - great stuff!

Ryan Randall

Solutions are easy. Understanding the problem, now, that's the hard part.

Frédéric BROUARD Old Hand Points: 315 More actions · Answer 11

Frédéric BROUARD

Old Hand

Points: 315

January 10, 2009 at 12:33 am

#924790

I hope it won't be the last !

A +

paolosaurus SSC Journeyman Points: 82 More actions · Answer 12

regarding the original query. It seems repetition of the characters is not allowed. This is therefore not a permutations calculator but is a combinations calculator.

kgresham SSC Enthusiast Points: 197 More actions · Answer 13

This uses a binary mask to select the unique sets where one of each character are present. It runs in about 14 seconds.

declare @t varchar(10) = 'ABCDEFGH'

;with src(t,n,p) as (

select substring(@t,1,1),1,power(2,0)

union all

select substring(@t,n+1,1),n+1,power(2,n)

from src

where n < len(@t)

)

select s1.t+s2.t+s3.t+s4.t+s5.t+s6.t+s7.t+s8.t

from src s1, src s2, src s3, src s4, src s5, src s6, src s7, src s8

where s1.p+s2.p+s3.p+s4.p+s5.p+s6.p+s7.p+s8.p=power(2,len(@t))-1

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 14

Frédéric BROUARD (1/8/2009)
This calculus can be done in only one query
(I think I am the first to demontsrate how to do that in one query only !) 😉
-- lest's assume that this table containes all datas to be permuted :
CREATE TABLE T_CMB (CMB_DATA VARCHAR(8))
-- let's assume that the joker character ; (dot comma) is not used inside the data :
INSERT INTO T_CMB VALUES ('ABC')
INSERT INTO T_CMB VALUES ('DEF')
INSERT INTO T_CMB VALUES ('GHI')
-- the following query does the permutations
WITH
T_DATA AS
(SELECT CMB_DATA, 1 AS COMBINAISON,
ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE,
COUNT(*) OVER() AS N
FROM T_CMB),
T_RECUR AS
(SELECT CAST(CMB_DATA AS VARCHAR(max)) +';' AS CMB_DATA, COMBINAISON, ORDRE, N
FROM T_DATA
UNION ALL
SELECT T1.CMB_DATA + ';' + T2.CMB_DATA, T2.COMBINAISON + 1, ROW_NUMBER() OVER(PARTITION BY T1.COMBINAISON ORDER BY T2.CMB_DATA) ORDRE, T1.N
FROM T_DATA AS T1
CROSS JOIN T_RECUR AS T2
WHERE T2.COMBINAISON < T1.N
-- this line must be delete if you want a repetitive permutation
AND T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'
),
T_COMBINE AS
(SELECT CMB_DATA, ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE
FROM T_RECUR
WHERE COMBINAISON = N),
T_N AS
(SELECT 1 AS N
UNION ALL
SELECT N + 1
FROM T_N
WHERE N + 1 <= ALL (SELECT LEN(CMB_DATA)
FROM T_COMBINE)),
T_SOL AS
(SELECT *, REVERSE(SUBSTRING(CMB_DATA, 1, N-1)) AS SOUS_CHAINE,
REVERSE(SUBSTRING(REVERSE(SUBSTRING(CMB_DATA, 1, N-1)), 1,
CASE
WHEN CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1 = -1 THEN LEN(CMB_DATA)
ELSE CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1
END)) AS DATA
FROM T_COMBINE
INNER JOIN T_N
ON SUBSTRING(CMB_DATA, N, 1) = ';')
SELECT DATA AS CMB_DATA, ORDRE AS PERMUTATION
FROM T_SOL
CMB_DATA PERMUTATION
------------------------- --------------------
ABC 1
DEF 1
GHI 1
ABC 2
GHI 2
DEF 2
DEF 3
ABC 3
GHI 3
DEF 4
GHI 4
ABC 4
GHI 5
ABC 5
DEF 5
GHI 6
DEF 6
ABC 6
If you want a permutation with repetitive datas, simply delete the 18e line :
AND T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'
You'll get :
CMB_DATA PERMUTATION
----------------------- --------------------
ABC 1
ABC 1
ABC 1
ABC 2
ABC 2
DEF 2
ABC 3
ABC 3
GHI 3
ABC 4
DEF 4
ABC 4
ABC 5
DEF 5
DEF 5
ABC 6
DEF 6
GHI 6
ABC 7
GHI 7
ABC 7
ABC 8
GHI 8
DEF 8
ABC 9
GHI 9
GHI 9
DEF 10
ABC 10
ABC 10
DEF 11
ABC 11
DEF 11
DEF 12
ABC 12
GHI 12
DEF 13
DEF 13
ABC 13
DEF 14
DEF 14
DEF 14
DEF 15
DEF 15
GHI 15
DEF 16
GHI 16
ABC 16
DEF 17
GHI 17
DEF 17
DEF 18
GHI 18
GHI 18
GHI 19
ABC 19
ABC 19
GHI 20
ABC 20
DEF 20
GHI 21
ABC 21
GHI 21
GHI 22
DEF 22
ABC 22
GHI 23
DEF 23
DEF 23
GHI 24
DEF 24
GHI 24
GHI 25
GHI 25
ABC 25
GHI 26
GHI 26
DEF 26
GHI 27
GHI 27
GHI 27
The french version is on my blog :
http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathema
CU
---
Frédéric BROUARD, Spécialiste modélisation, bases de données, optimisation, langage SQL.
Le site sur le langage SQL et les S.G.B.D. relationnels : http://sqlpro.developpez.com/[/url]
Expert SQL Server http://www.sqlspot.com : audit, optimisation, tuning, formation
* * * * * Enseignant au CNAM PACA et à l'ISEN à Toulon * * * * *

At a "9" count, you're also the first to get beat by the While loop by a factor of more than 30 even with discarded results enabled. 😉

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)