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
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.
- 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.
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)