Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 

Generating Permutations in T-SQL

By Eli Leiba,

This article describes how to dynamically generate all possible permutations for a given set of values. In a T-SQL stored procedure, the set of values is coded directly (as a fixed derived table) inside the Procedure's code to gain optimal performance

In many cases, specifically in QA units , programs need to be tested for all possible input values. The parameters all possible combinations can be considered as a set of values. The process I show here is a method for generating all possible permutations for a fixed and known set of values. The integer parameter n for the procedure is a number <= number of set elements that will limit the permutations calculation for first n elements in the set. The number of permutations will result in n! = P(n)

The T-SQL stored procedure

The stored procedure assumes that the given set of values is given in the following format

     SELECT 0 as X , v1 as Y    union all
                     1 ,         v2  union all 
                    2,          v3  union all 
                     .
                    .
                    .
                  N-1 ,      vn         

where X is an alias for a running index and Y is the actual set value. I'll refer to this query as S for the next explanation

The procedure takes this SELECT as a base "table" and generates a dynamic SQL statement in the following format

   SELECT    T1.Y, T2.Y, T3.Y,......................Tn.Y
   FROM S T1, S T2,           .........., S Tn
   where   T1.X < n AND 
                T2.X < n AND 
                .
               .
                Tn.X < n AND 
                Ti.X <> Tj.X    (FOR all i <> j , i,j <=n, all possible clauses)

This query will give all permutation combinations for the first n Y values in S because the Cartesian product of all Si is constrained to be less than n and all X values are not equal to one another. Note that there are n Ti.X < n where clause and n!/ [(n-2)!*2 ] = (n/2)* (n-1) Ti.X <> Tj.X clauses (all possible i,j selections where i<>j, i,j <=n)

The procedure's code

(I coded A,B,C,D,.....J as the set values without losing the generality of the program - replace the values for your needs)

Create Proc sp_permutate (@n smallint)
as
begin 
 set nocount on 
 declare @sqlStmt varchar(4000)
 declare @base varchar(300)
 declare @list varchar(300)
 declare @i int
 declare @j int

 set @base = '(' + 
	'SELECT 0 AS X, ' + '''' + 'A' + '''' + ' as Y ' + ' UNION ALL ' + 
	'SELECT 1 , ' + '''' + 'B' + '''' +  ' UNION ALL ' + 
	'SELECT 2 , ' + '''' + 'C' + '''' +  ' UNION ALL ' + 
	'SELECT 3 , ' + '''' + 'D' + '''' + ' UNION ALL ' + 
	'SELECT 4 , ' + '''' + 'E' + '''' + ' UNION ALL ' + 
	'SELECT 5 , ' + '''' + 'F' + '''' + ' UNION ALL ' + 
	'SELECT 6 , ' + '''' + 'G' + '''' + ' UNION ALL ' + 
	'SELECT 7 , ' + '''' + 'H' + '''' + ' UNION ALL ' + 
	'SELECT 8 , ' + '''' + 'I' + '''' + ' UNION ALL ' + 
	'SELECT 9 , ' + '''' + 'J' + '''' +  
	' ) '

 -- DO the select list
 set @i=1
 set @list = 'SELECT '
 while @i <= @n begin 
     SET @list = @list + 'T' + convert (varchar(2),@i) + '.Y,'
     SET @i = @i + 1
 end

 set @list = substring (@list,1,len (@list)-1)
 set @list = @list + ' FROM ' 
 
 -- DO the FROM list
 set @sqlStmt = @list 
 set @i=1
  while @i <= @n begin 
     SET @sqlStmt = @sqlStmt + @base +' as T' + convert (varchar(2),@i) +' ,'
     SET @i = @i + 1
 end
 set @sqlStmt = substring (@sqlStmt,1,len (@sqlStmt)-1)

 -- DO first where clauses
 set @sqlStmt = @sqlStmt + ' WHERE ' 
 set @i=1
  while @i <= @n begin 
     SET @sqlStmt = @sqlStmt + 'T' + convert (varchar(2),@i) + 
	'.X < ' + convert (varchar(2),@n) + ' AND ' 
     SET @i = @i + 1
 end

 -- continue the WHERE clauses
 set @i=1
 while @i < @n begin 
     set @j = @i + 1 
     while @j <= @n begin 
       SET @sqlStmt = @sqlStmt + 'T' + convert (varchar(2),@i) + 
	'.X <> ' + 'T' + convert (varchar(2),@j) + '.X AND ' 
        SET @j = @j + 1
     end
     SET @i = @i + 1
 end
 set @sqlStmt = substring (@sqlStmt,1,len (@sqlStmt)-4) 

 print @sqlStmt
 exec (@sqlStmt)

 set nocount off
end
go

Conclusion

The TSQL code that I presented here can be a generic tool for generating permutations for a fixed and known set of values a generated SQL that constraints the Cartesian product for N buffers for the given set S with all the needed constraints to produce the permutations This process can be very useful for automating the generations of permutations for program unit checks and QA tests.

Notes :

  • exec sp_permutate 7 will produce the 7! = 5040 all possible permutations for A,B,C,D,E,F,G
  • Note that if you try to replace the base SELECT with a pre-defined view and try to run the procedure , the MSSQL optimizer can fail because a plan cannot be generated. I the code is coded directly in the procedure code, this problem will not occur.

Download the code

Eli Leiba works at Israel Electric Company as a Senior Application DBA in Oracle and MS SQL Server. He also has certifications from Microsoft and BrainBench in Oracle and SQL Server database administration and implementation. Mr. Leiba holds a B.S. in Computer Science since 1991 and has 14 years' experience working in the databases field. Additionally Mr. Leiba teaches SQL Server DBA and Development courses at Microsoft CTEC and also serves as a senior database consultant for several Israeli start-up companies. (e-mail: Eli.Leiba@2cher.com)

Total article views: 11068 | Views in the last 30 days: 11
 
Related Articles
SCRIPT

Generating permutations

This script shows one on ways of generating permutations.

SCRIPT

Generating permutations - procedure

This procedure prepares a query for generating permutations of n-numbers set and executes it.

BLOG

SQL Server – Generating PERMUTATIONS using T-Sql

Were you ever asked to generate string Permutations using TSql? I was recently asked to do so, and t...

BLOG

SQL Server – Generating PERMUTATIONS using T-Sql

Were you ever asked to generate string Permutations using TSql? I was recently asked to do so, and t...

FORUM

Generating Permutations in T-SQL

Comments posted to this topic are about the content posted at http://www.sqlservercentral.com/column...

Tags
advanced querying    
t-sql    
 
Contribute

Join the most active online SQL Server Community

SQL knowledge, delivered daily, free:

Email address:  

You make SSC a better place

As a member of SQLServerCentral, you get free access to loads of fresh content: thousands of articles and SQL scripts, a library of free eBooks, a weekly database news roundup, a great Q & A platform… And it’s our huge, buzzing community of SQL Server Professionals that makes it such a success.

Join us!

Steve Jones
Editor, SQLServerCentral.com

Already a member? Jump in:

Email address:   Password:   Remember me: Forgotten your password?
Steve Jones