SQLServerCentral / Discuss Content Posted by Eli Leiba / Article Discussions / Article Discussions by Author / Generating Permutations in T-SQL / Latest Posts

RE: Generating Permutations in T-SQL

paolosaurus — Tue, 15 Jan 2013 13:19:09 GMT

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.

RE: Generating Permutations in T-SQL

Frédéric BROUARD — Sat, 10 Jan 2009 00:33:20 GMT

I hope it won't be the last !A +

RE: Generating Permutations in T-SQL

RyanRandall — Fri, 09 Jan 2009 16:35:58 GMT

Thanks Frédéric :)I dare say that's my first ever 'publication' in a foreign language - great stuff!

RE: Generating Permutations in T-SQL

Frédéric BROUARD — Fri, 09 Jan 2009 15:23:44 GMT

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

RE: Generating Permutations in T-SQL

RyanRandall — Fri, 09 Jan 2009 04:39:38 GMT

[quote][b]Frédéric BROUARD (1/8/2009)[/b] ... [/quote]Here's something similar for comparison, making use of powers of 2 rather than LIKE, and XML rather than string manuipulation.[code]--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>' + 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 valueFROM d CROSS APPLY xml.nodes('//x') T(c)--/[/code]

RE: Generating Permutations in T-SQL

Frédéric BROUARD — Thu, 08 Jan 2009 08:32:44 GMT

[b]This calculus can be done in only one query[/b](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 :[code]CREATE TABLE T_CMB (CMB_DATA VARCHAR(8))[/code]-- let's assume that the joker character [size="3"][color="AAAA"][b];[/b][/color][/size] (dot comma) is not used inside the data :[code]INSERT INTO T_CMB VALUES ('ABC')INSERT INTO T_CMB VALUES ('DEF')INSERT INTO T_CMB VALUES ('GHI')[/code]-- the following query does the permutations[code]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 [/code] [code]CMB_DATA PERMUTATION------------------------- --------------------ABC 1DEF 1GHI 1ABC 2GHI 2DEF 2DEF 3ABC 3GHI 3DEF 4GHI 4ABC 4GHI 5ABC 5DEF 5GHI 6DEF 6ABC 6[/code]If you want a permutation with repetitive datas, simply delete the 18e line : [code]AND T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'[/code]You'll get :[code]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[/code]The french version is on my blog :[url=http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathema]http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathema[/url]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 : [url=http://sqlpro.developpez.com/]http://sqlpro.developpez.com/[/url]Expert SQL Server [url=http://www.sqlspot.com]http://www.sqlspot.com[/url] : audit, optimisation, tuning, formation* * * * * Enseignant au CNAM PACA et à l'ISEN à Toulon * * * * *

RE: Generating Permutations in T-SQL

Dennis D. Allen — Mon, 06 Nov 2006 09:35:00 GMT

Just to toss my hat in the ring...create procedure dbo.usp_permutate @charset nvarchar(256) = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'asset nocount on-- a set of all values in the charsetcreate table #set ( k int, v nchar(1) )declare @i int, @c nvarchar(5)declare @select nvarchar(4000)declare @from nvarchar(4000)select @i = 1 , @select = 's1.v ' , @from = '#set s1 'insert into #set ( k, v ) values ( 1, substring(@charset, @i, 1) )while @i < len(@charset) begin set @i = @i + 1 set @c = convert(nvarchar(5), @i) insert into #set ( k, v ) values ( 1, substring(@charset, @i, 1) ) set @select = @select + '+ s' + @c + '.v ' set @from = @from + 'join #set s' + @c + ' on s' + @c + '.k = s1.k 'end-- output queryexec( 'select ' + @select + 'as permutation from ' + @from + 'order by permutation' )-- clean updrop table #set

RE: Generating Permutations in T-SQL

RyanRandall — Tue, 21 Mar 2006 06:05:00 GMT

Hi all,I wrote this for fun, and thought I'd share it here, since it's vaguely related. It's interesting mathematics (in that the method works) if nothing else. If you set @i below to your set size, then a list of all combinations of numbers is returned (as a varchar). e.g. @i = 3 gives:210 201 120 021 102 012 The timings on my pc are:

Size Seconds Rows7 0 50408 1 403209 6 36288010 60 3628800

--This SQL script is safe to run--InputsDECLARE @i TINYINTSET @i = 7 --set size

--ValidationIF @i > 10 BEGIN PRINT 'i is too large' SET @i = 0 END

--DeclarationsCREATE TABLE #t (n TINYINT, v VARCHAR(10))CREATE CLUSTERED INDEX #ix_t ON #t (n)DECLARE @n TABLE (i TINYINT) --numbers tableDECLARE @Counter INT

--InitialisationsINSERT @n SELECT 0INSERT #t SELECT 0, '0 'SET @Counter = 1

--Loop for each integer from 1 to @i-1WHILE @Counter <= @i - 1BEGIN INSERT @n SELECT @Counter INSERT #t SELECT @Counter, STUFF(v, i+1, 0, @Counter) FROM #t, @n WHERE n = @Counter - 1 SET @Counter = @Counter + 1END

--Select results we're interested inSELECT v FROM #t WHERE n = @i - 1

--Tidy upDROP TABLE #t

RE: Generating Permutations in T-SQL

CELKO — Mon, 31 Oct 2005 14:57:00 GMT

Technically, you should be using Standard SQL/PSM instead of proprietary T-SQL, since it is the proper way to implement procedures.

But the whole idea of SQL is that we are using a declarative language and not a procedural one. The nice thing about building a table is that you do it one time only and you can use any procedural language you wish -- even T-SQL.

Of course 10! = 3,628,800 which is a fair size table, but not impossible.

RE: Generating Permutations in T-SQL

Eli Leiba — Mon, 31 Oct 2005 14:10:00 GMT

SQL 2005 has CTE that can do the permutations more easy

I coded for SQL-2000 ,

If you use a phisical table and not a "memory table" like

(select 1 union select 2 union ........)

then the optimizer will crush for more than 10 join with the table

to itself so memory derived tables must be used on this one

RE: Generating Permutations in T-SQL

Michael Wang — Mon, 24 Oct 2005 10:59:00 GMT

I see nothing wrong with procedural code if implemeneted properly. The original code has the problem of being too complex and is also limited in scope. I ran it up to 7, beyond which my SQL2000 will not be able to generate a plan. The procedure below is inspired by the original code but is drastically different: it handles large set really fast and dynamic SQL statement is short and recursive (use @debug = 1 to see it).

To use it, you need to store your values in a table with a single column 'x'. This procedure permutes r out of n. Of course you need to make sure r<=n, and be aware that the result set could be substantial (n! / (n-r)! permutations).

It may not be useful, but just for fun.

Create Proc sp_permutate (@n smallint, @t varchar(8), @debug bit = 0)asbegin set nocount on declare @sqlStmt varchar(4000), @delim varchar(2) declare @i int declare @j int

if @debug = 1 set @delim = char(10) else set @delim = ''set @sqlStmt = 'SELECT x' + cast(@n as varchar(2)) + '=X from ' + @t + @delimset @i = @n -1

while @i > 0Begin set @j = @n set @sqlStmt = 'SELECT x' + cast(@i as varchar(2)) + '=X, T.* from ' + @t + ' join (' + @delim + @sqlStmt + ') T on x<>x' + cast(@j as varchar(2)) set @j = @j - 1 while @j > @i Begin set @sqlStmt = @sqlStmt + ' and x<>x' + cast(@j as varchar(2)) set @j = @j - 1 End set @sqlStmt = @sqlStmt + @delim set @i = @i - 1End

print @sqlStmt exec (@sqlStmt)

set nocount offendgo

RE: Generating Permutations in T-SQL

HelloFOFO — Wed, 19 Oct 2005 20:25:00 GMT

I think it is better to limit the input parameter @n <= 10.

I modify this proc in my SQL 2000 Query Analyzer

just change the length of all parameters such as @sqlStmt,@base etc. to

5000

Then,I used 11 as input parameter and the Query Analyzer return an error:

can't generate query plan......

But I didn't try 10......

RE: Generating Permutations in T-SQL

CELKO — Wed, 19 Oct 2005 11:31:00 GMT

I have to finish my own posting. If you have SQL-2005 and you can use a CTE for the Sequence table.

Now load the results in a table. Perm(i1, i2, ..in) with a primary key of all columns. Once you have this table for all permutations of (n), you can create a set of views like this whch will give you the permutatiosn for (j < n). For example (j=5) is done with this:

CREATE VIEW Perm5 (i1, i2, i3, i4, i5)ASSELECT DISTINCT i1, i2, i3, i4, i5 FROM Perm WHERE i1 <= 5 AND i2 <= 5 AND i3 <= 5 AND i4 <= 5 AND i5 <= 5;

Think in sets and not in procedrual code.

RE: Generating Permutations in T-SQL

CELKO — Wed, 19 Oct 2005 09:52:00 GMT

Forget that horrible procdural code. Let Sequence be a table of (n) integers from 1 to (n):

SELECT S1.i, S2.i, .., Sn1.i FROM Sequence AS S1, Sequence AS S2, ..Sequence AS Sn WHERE S1.i NOT IN (S2.i, .., Sn.i) AND S2.i NOT IN (S1.i, .., Sn.i) . AND Sn.i NOT IN (S1.i, .., S[n-1].i);

There are some other tricks for assigning a combination number to the rows.

Most of this guy's poostngs have been procedural code and not good SQL at all.

RE: Generating Permutations in T-SQL

John Scarborough — Wed, 19 Oct 2005 08:56:00 GMT

Nice article! I really had to "think" my way through this one, but its likely to be very useful.

Generating Permutations in T-SQL

Eli Leiba — Thu, 08 Sep 2005 21:40:00 GMT

Comments posted to this topic are about the content posted at http://www.sqlservercentral.com/columnists/eleiba/generatingpermutationsintsql.asp