Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase ««12

Generating Permutations in T-SQL Expand / Collapse
Author
Message
Posted Thursday, January 08, 2009 8:32 AM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Saturday, October 05, 2013 8:27 AM
Points: 15, Visits: 118
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/
Expert SQL Server http://www.sqlspot.com : audit, optimisation, tuning, formation
* * * * * Enseignant au CNAM PACA et à l'ISEN à Toulon * * * * *



Post #632451
Posted Friday, January 09, 2009 4:39 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Tuesday, May 29, 2012 11:22 AM
Points: 1,755, Visits: 4,652
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.
Post #633249
Posted Friday, January 09, 2009 3:23 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Saturday, October 05, 2013 8:27 AM
Points: 15, Visits: 118
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



Post #633955
Posted Friday, January 09, 2009 4:35 PM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Tuesday, May 29, 2012 11:22 AM
Points: 1,755, Visits: 4,652
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.
Post #633997
Posted Saturday, January 10, 2009 12:33 AM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Saturday, October 05, 2013 8:27 AM
Points: 15, Visits: 118
I hope it won't be the last !

A +



Post #634104
Posted Tuesday, January 15, 2013 1:19 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Thursday, May 09, 2013 6:58 PM
Points: 2, Visits: 41
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.


Post #1407455
« Prev Topic | Next Topic »

Add to briefcase ««12

Permissions Expand / Collapse