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 Friday, January 9, 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, May 23, 2015 12:35 AM
Points: 15, Visits: 119
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, January 29, 2015 10:58 AM
Points: 2, Visits: 51
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
Posted Friday, May 22, 2015 4:45 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Friday, May 22, 2015 4:48 PM
Points: 3, Visits: 165
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
Post #1688232
Posted Friday, May 22, 2015 6:19 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 7:05 AM
Points: 37,459, Visits: 34,321
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/
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."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1688236
« Prev Topic | Next Topic »

Add to briefcase ««12

Permissions Expand / Collapse