Click here to monitor SSC
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Generating Permutations in T-SQL


Generating Permutations in T-SQL

Author
Message
Frédéric BROUARD
Frédéric BROUARD
Grasshopper
Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)

Group: General Forum Members
Points: 15 Visits: 127
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 !) Wink

-- 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/
Expert SQL Server http://www.sqlspot.com : audit, optimisation, tuning, formation
* * * * * Enseignant au CNAM PACA et à l'ISEN à Toulon * * * * *



RyanRandall
RyanRandall
SSCommitted
SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)

Group: General Forum Members
Points: 1761 Visits: 4652
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
Frédéric BROUARD
Grasshopper
Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)

Group: General Forum Members
Points: 15 Visits: 127
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
RyanRandall
SSCommitted
SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)

Group: General Forum Members
Points: 1761 Visits: 4652
Thanks Frédéric Smile

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
Frédéric BROUARD
Grasshopper
Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)

Group: General Forum Members
Points: 15 Visits: 127
I hope it won't be the last !

A +



paolosaurus
paolosaurus
Forum Newbie
Forum Newbie (2 reputation)Forum Newbie (2 reputation)Forum Newbie (2 reputation)Forum Newbie (2 reputation)Forum Newbie (2 reputation)Forum Newbie (2 reputation)Forum Newbie (2 reputation)Forum Newbie (2 reputation)

Group: General Forum Members
Points: 2 Visits: 67
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
kgresham
Forum Newbie
Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)

Group: General Forum Members
Points: 7 Visits: 187
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
Jeff Moden
SSC-Forever
SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)

Group: General Forum Members
Points: 45432 Visits: 39942
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 !) Wink

-- 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/
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.
Although they tell us that they want it real bad, our primary goal is to ensure that we dont actually give it to them that way.
Although change is inevitable, change for the better is not.
Just because you can do something in PowerShell, doesnt mean you should. Wink

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
kgresham
kgresham
Forum Newbie
Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)Forum Newbie (7 reputation)

Group: General Forum Members
Points: 7 Visits: 187
I have a new solution. This one is Recursive CTE but only builds valid solutions instead of all solutions. It will produce the 3.6 million permutations for a 10 character string in 3:02 minutes.

declare @t varchar(10) = 'ABCDEFGHIJ'

;with s(t,n) as (
select substring(@t,1,1),1
union all
select substring(@t,n+1,1),n+1
from s where n<len(@t)
)
,j(t) as (
select cast(t as varchar(10)) from s
union all
select cast(j.t+s.t as varchar(10))
from j,s where patindex('%'+s.t+'%',j.t)=0
)
select t from j where len(t)=len(@t)
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search