

SSC Rookie
Group: General Forum Members
Last Login: Wednesday, February 4, 2015 12:15 PM
Points: 47,
Visits: 19





SSC 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




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




SSC 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! / (nr)! 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




SSC 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 SQL2000 , 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




SSCommitted
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 @i1 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.




SSCEnthusiastic
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




Grasshopper
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, N1)) AS SOUS_CHAINE, REVERSE(SUBSTRING(REVERSE(SUBSTRING(CMB_DATA, 1, N1)), 1, CASE WHEN CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N1)))  1 = 1 THEN LEN(CMB_DATA) ELSE CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N1)))  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 * * * * *




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




Grasshopper
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



