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: Wednesday, February 4, 2015 12:15 PM
Points: 47, Visits: 19
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 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: Wednesday, February 4, 2015 12:15 PM
Points: 47, 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

Post #233957
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
Posted Thursday, January 8, 2009 8:32 AM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Saturday, May 23, 2015 12:35 AM
Points: 15, Visits: 119
This calculus can be done in only one query

(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 :
CREATE TABLE T_CMB (CMB_DATA VARCHAR(8))

-- let's assume that the joker character ; (dot comma) is not used inside the data :
INSERT INTO T_CMB VALUES ('ABC')
INSERT INTO T_CMB VALUES ('DEF')
INSERT INTO T_CMB VALUES ('GHI')

-- the following query does the permutations
WITH
T_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 PERMUTATION
FROM T_SOL



CMB_DATA                  PERMUTATION
------------------------- --------------------
ABC 1
DEF 1
GHI 1

ABC 2
GHI 2
DEF 2

DEF 3
ABC 3
GHI 3

DEF 4
GHI 4
ABC 4

GHI 5
ABC 5
DEF 5

GHI 6
DEF 6
ABC 6

If you want a permutation with repetitive datas, simply delete the 18e line :
AND  T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'

You'll get :

CMB_DATA                PERMUTATION
----------------------- --------------------
ABC 1
ABC 1
ABC 1

ABC 2
ABC 2
DEF 2

ABC 3
ABC 3
GHI 3

ABC 4
DEF 4
ABC 4

ABC 5
DEF 5
DEF 5

ABC 6
DEF 6
GHI 6

ABC 7
GHI 7
ABC 7

ABC 8
GHI 8
DEF 8

ABC 9
GHI 9
GHI 9

DEF 10
ABC 10
ABC 10

DEF 11
ABC 11
DEF 11

DEF 12
ABC 12
GHI 12

DEF 13
DEF 13
ABC 13

DEF 14
DEF 14
DEF 14

DEF 15
DEF 15
GHI 15

DEF 16
GHI 16
ABC 16

DEF 17
GHI 17
DEF 17

DEF 18
GHI 18
GHI 18

GHI 19
ABC 19
ABC 19

GHI 20
ABC 20
DEF 20

GHI 21
ABC 21
GHI 21

GHI 22
DEF 22
ABC 22

GHI 23
DEF 23
DEF 23

GHI 24
DEF 24
GHI 24

GHI 25
GHI 25
ABC 25

GHI 26
GHI 26
DEF 26

GHI 27
GHI 27
GHI 27

The french version is on my blog :
http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathema

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 : http://sqlpro.developpez.com/
Expert SQL Server http://www.sqlspot.com : audit, optimisation, tuning, formation
* * * * * Enseignant au CNAM PACA et à l'ISEN à Toulon * * * * *



Post #632451
Posted Friday, January 9, 2009 4:39 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Tuesday, May 29, 2012 11:22 AM
Points: 1,755, Visits: 4,652
Frédéric BROUARD (1/8/2009) ...


Here's something similar for comparison, making use of powers of 2 rather than LIKE, and XML rather than string manuipulation.


--preparation
IF OBJECT_ID('tempdb.dbo.#t1') IS NOT NULL DROP TABLE #t1
GO
--/

--structure
CREATE TABLE #t1 (x VARCHAR(MAX))
--/

--data
INSERT INTO #t1 VALUES ('ABC')
INSERT INTO #t1 VALUES ('DEF')
INSERT INTO #t1 VALUES ('GHI')
--/

--parameters
DECLARE @AllowDuplicates BIT
SET @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 value
FROM d CROSS APPLY xml.nodes('//x') T(c)
--/




Ryan Randall

Solutions are easy. Understanding the problem, now, that's the hard part.
Post #633249
Posted Friday, January 9, 2009 3:23 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Saturday, May 23, 2015 12:35 AM
Points: 15, Visits: 119
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



Post #633955
« Prev Topic | Next Topic »

Add to briefcase 12»»

Permissions Expand / Collapse