Click here to monitor SSC
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Generating Permutations in T-SQL


Generating Permutations in T-SQL

Author
Message
Eli Leiba
Eli Leiba
Valued Member
Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)

Group: General Forum Members
Points: 51 Visits: 19
Comments posted to this topic are about the content posted at http://www.sqlservercentral.com/columnists/eleiba/generatingpermutationsintsql.asp
John Scarborough
John Scarborough
SSC Veteran
SSC Veteran (290 reputation)SSC Veteran (290 reputation)SSC Veteran (290 reputation)SSC Veteran (290 reputation)SSC Veteran (290 reputation)SSC Veteran (290 reputation)SSC Veteran (290 reputation)SSC Veteran (290 reputation)

Group: General Forum Members
Points: 290 Visits: 52
Nice article! I really had to "think" my way through this one, but its likely to be very useful.

John Scarborough
MCDBA, MCSA
HelloFOFO
HelloFOFO
SSC-Enthusiastic
SSC-Enthusiastic (161 reputation)SSC-Enthusiastic (161 reputation)SSC-Enthusiastic (161 reputation)SSC-Enthusiastic (161 reputation)SSC-Enthusiastic (161 reputation)SSC-Enthusiastic (161 reputation)SSC-Enthusiastic (161 reputation)SSC-Enthusiastic (161 reputation)

Group: General Forum Members
Points: 161 Visits: 76

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


Michael Wang
Michael Wang
SSC Rookie
SSC Rookie (31 reputation)SSC Rookie (31 reputation)SSC Rookie (31 reputation)SSC Rookie (31 reputation)SSC Rookie (31 reputation)SSC Rookie (31 reputation)SSC Rookie (31 reputation)SSC Rookie (31 reputation)

Group: General Forum Members
Points: 31 Visits: 37

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)
as
begin
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 + @delim
set @i = @n -1

while @i > 0
Begin
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 - 1
End

print @sqlStmt
exec (@sqlStmt)

set nocount off
end
go





Eli Leiba
Eli Leiba
Valued Member
Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)Valued Member (51 reputation)

Group: General Forum Members
Points: 51 Visits: 19

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


RyanRandall
RyanRandall
SSCommitted
SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)

Group: General Forum Members
Points: 1761 Visits: 4652

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 Rows
7 0 5040
8 1 40320
9 6 362880
10 60 3628800

--This SQL script is safe to run
--Inputs
DECLARE @i TINYINT
SET @i = 7 --
set size

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

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

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

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

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

--Tidy up
DROP TABLE #t



Ryan Randall

Solutions are easy. Understanding the problem, now, that's the hard part.
Dennis D. Allen
Dennis D. Allen
SSC-Enthusiastic
SSC-Enthusiastic (117 reputation)SSC-Enthusiastic (117 reputation)SSC-Enthusiastic (117 reputation)SSC-Enthusiastic (117 reputation)SSC-Enthusiastic (117 reputation)SSC-Enthusiastic (117 reputation)SSC-Enthusiastic (117 reputation)SSC-Enthusiastic (117 reputation)

Group: General Forum Members
Points: 117 Visits: 163
Just to toss my hat in the ring...

create procedure dbo.usp_permutate
@charset nvarchar(256) = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
as

set nocount on

-- a set of all values in the charset
create 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 query
exec( 'select ' + @select + 'as permutation from ' + @from + 'order by permutation' )


-- clean up
drop table #set
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search