Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase 12»»

Generating Permutations in T-SQL Expand / Collapse
Author
Message
Posted Thursday, September 8, 2005 9:40 PM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Monday, February 17, 2014 2:05 AM
Points: 47, Visits: 18
Comments posted to this topic are about the content posted at http://www.sqlservercentral.com/columnists/eleiba/generatingpermutationsintsql.asp
Post #218243
Posted Wednesday, October 19, 2005 8:56 AM


SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Thursday, July 24, 2014 1:52 PM
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
Post #230201
Posted Wednesday, October 19, 2005 9:52 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Friday, September 19, 2014 5:15 PM
Points: 1,945, Visits: 3,008

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.

 



Books in Celko Series for Morgan-Kaufmann Publishing
Analytics and OLAP in SQL
Data and Databases: Concepts in Practice
Data, Measurements and Standards in SQL
SQL for Smarties
SQL Programming Style
SQL Puzzles and Answers
Thinking in Sets
Trees and Hierarchies in SQL
Post #230247
Posted Wednesday, October 19, 2005 11:31 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Friday, September 19, 2014 5:15 PM
Points: 1,945, Visits: 3,008

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

 



Books in Celko Series for Morgan-Kaufmann Publishing
Analytics and OLAP in SQL
Data and Databases: Concepts in Practice
Data, Measurements and Standards in SQL
SQL for Smarties
SQL Programming Style
SQL Puzzles and Answers
Thinking in Sets
Trees and Hierarchies in SQL
Post #230326
Posted Wednesday, October 19, 2005 8:25 PM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Wednesday, December 12, 2012 6:21 PM
Points: 161, Visits: 73

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

Post #230502
Posted Monday, October 24, 2005 10:59 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Sunday, April 10, 2011 11:42 AM
Points: 25, 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

 




Post #231750
Posted Monday, October 31, 2005 2:10 PM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Monday, February 17, 2014 2:05 AM
Points: 47, Visits: 18

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

Post #233957
Posted Monday, October 31, 2005 2:57 PM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Friday, September 19, 2014 5:15 PM
Points: 1,945, Visits: 3,008

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.

 

 



Books in Celko Series for Morgan-Kaufmann Publishing
Analytics and OLAP in SQL
Data and Databases: Concepts in Practice
Data, Measurements and Standards in SQL
SQL for Smarties
SQL Programming Style
SQL Puzzles and Answers
Thinking in Sets
Trees and Hierarchies in SQL
Post #233969
Posted Tuesday, March 21, 2006 6:05 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Tuesday, May 29, 2012 11:22 AM
Points: 1,755, Visits: 4,652

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.
Post #267234
Posted Monday, November 6, 2006 9:35 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Tuesday, June 5, 2012 12:03 PM
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
Post #320707
« Prev Topic | Next Topic »

Add to briefcase 12»»

Permissions Expand / Collapse