Recent PostsRecent Posts Popular TopicsPopular Topics
 Home Search Members Calendar Who's On

 Generating Permutations in T-SQL Rate Topic Display Mode Topic Options
Author
 Message
 Posted Friday, January 9, 2009 4:35 PM
 SSCommitted 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 RandallSolutions are easy. Understanding the problem, now, that's the hard part.
Post #633997
 Posted Saturday, January 10, 2009 12:33 AM
 Grasshopper Group: General Forum Members Last Login: Saturday, September 19, 2015 7:50 AM Points: 15, Visits: 127
 I hope it won't be the last !A +
Post #634104
 Posted Tuesday, January 15, 2013 1:19 PM
 Forum Newbie Group: General Forum Members Last Login: Thursday, November 17, 2016 3:15 PM Points: 2, Visits: 64
 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 Group: General Forum Members Last Login: Saturday, July 2, 2016 11:43 AM Points: 5, 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 allselect substring(@t,n+1,1),n+1,power(2,n)from srcwhere n < len(@t))select s1.t+s2.t+s3.t+s4.t+s5.t+s6.t+s7.t+s8.tfrom src s1, src s2, src s3, src s4, src s5, src s6, src s7, src s8where 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-Forever Group: General Forum Members Last Login: Yesterday @ 2:41 PM Points: 42,081, Visits: 39,473
 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`WITHT_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 PERMUTATIONFROM T_SOL ` `CMB_DATA PERMUTATION------------------------- --------------------ABC 1DEF 1GHI 1ABC 2GHI 2DEF 2DEF 3ABC 3GHI 3DEF 4GHI 4ABC 4GHI 5ABC 5DEF 5GHI 6DEF 6ABC 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 1ABC 1ABC 1ABC 2ABC 2DEF 2ABC 3ABC 3GHI 3ABC 4DEF 4ABC 4ABC 5DEF 5DEF 5ABC 6DEF 6GHI 6ABC 7GHI 7ABC 7ABC 8GHI 8DEF 8ABC 9GHI 9GHI 9DEF 10ABC 10ABC 10DEF 11ABC 11DEF 11DEF 12ABC 12GHI 12DEF 13DEF 13ABC 13DEF 14DEF 14DEF 14DEF 15DEF 15GHI 15DEF 16GHI 16ABC 16DEF 17GHI 17DEF 17DEF 18GHI 18GHI 18GHI 19ABC 19ABC 19GHI 20ABC 20DEF 20GHI 21ABC 21GHI 21GHI 22DEF 22ABC 22GHI 23DEF 23DEF 23GHI 24DEF 24GHI 24GHI 25GHI 25ABC 25GHI 26GHI 26DEF 26GHI 27GHI 27GHI 27`The french version is on my blog :http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathemaCU---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." Helpful Links:How to post code problemsHow to post performance problems
Post #1688236
 Posted Tuesday, June 2, 2015 8:52 PM
 Forum Newbie Group: General Forum Members Last Login: Saturday, July 2, 2016 11:43 AM Points: 5, 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
Post #1691022

 Permissions