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 Thursday, January 08, 2009 8:32 AM
 Grasshopper 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`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 * * * * *
Post #632451
 Posted Friday, January 09, 2009 4:39 AM
 SSCommitted 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.`--preparationIF OBJECT_ID('tempdb.dbo.#t1') IS NOT NULL DROP TABLE #t1GO--/--structureCREATE TABLE #t1 (x VARCHAR(MAX))--/--dataINSERT INTO #t1 VALUES ('ABC')INSERT INTO #t1 VALUES ('DEF')INSERT INTO #t1 VALUES ('GHI')--/--parametersDECLARE @AllowDuplicates BITSET @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 + '' AS x FROM b UNION ALL SELECT c.marker + b.marker, c.level + 1, c.x + '' + b.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 valueFROM d CROSS APPLY xml.nodes('//x') T(c)--/` Ryan RandallSolutions are easy. Understanding the problem, now, that's the hard part.
Post #633249
 Posted Friday, January 09, 2009 3:23 PM
 Grasshopper 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 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, 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 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

 Permissions