If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.

 > Factorial Permutations, Without a Cursor?

 carlmal Registered User Join Date: Jul 2004 Location: Edmonton, Canada Posts: 72
Factorial Permutations, Without a Cursor?

 You folks always tell me to do as much as I can with set based operations and get rid of those damn cursors, so that is what I would like to do, but I can't really see any way to get around it. What I have to do is generate all the permutations for 6 values without having any values repeated in each combination (6 factorial, 6x5x4x3x2x1=720 permutations). Currently I have this job that takes 1-3 seconds to run. Code: ```ALTER PROCEDURE [dbo].[proc_SAHSGenComb2] AS DECLARE @pos1 INT DECLARE @pos2 INT DECLARE @pos3 INT DECLARE @pos4 INT DECLARE @pos5 INT DECLARE @pos6 INT DECLARE @currID INT DECLARE @currSort SMALLINT DECLARE @combID INT DECLARE curSeq CURSOR FAST_FORWARD FOR SELECT WKLD_ID FROM TSA_HS_WKLD ORDER BY HUMP_CUT_ORD OPEN curSeq FETCH NEXT FROM curSeq INTO @currID SET @currSort = 1 WHILE @@FETCH_STATUS = 0 BEGIN INSERT INTO TSA_HS_SEQ (WKLD_ID, CURR_SEQ) VALUES (@currID, @currSort) SET @currSort = @currSort + 1 FETCH NEXT FROM curSeq INTO @currID END CLOSE curSeq DEALLOCATE curSeq SET @combID = 1 DECLARE curPos1 CURSOR FAST_FORWARD FOR SELECT WKLD_ID FROM TSA_HS_SEQ WHERE CURR_SEQ <= 6 ORDER BY CURR_SEQ OPEN curPos1 FETCH NEXT FROM curPos1 INTO @pos1 WHILE @@FETCH_STATUS = 0 BEGIN DECLARE curPos2 CURSOR FAST_FORWARD FOR SELECT WKLD_ID FROM TSA_HS_SEQ WHERE WKLD_ID <> @pos1 AND CURR_SEQ <= 6 ORDER BY CURR_SEQ OPEN curPos2 FETCH NEXT FROM curPos2 INTO @pos2 WHILE @@FETCH_STATUS = 0 BEGIN DECLARE curPos3 CURSOR FAST_FORWARD FOR SELECT WKLD_ID FROM TSA_HS_SEQ WHERE WKLD_ID NOT IN (@pos1,@pos2) AND CURR_SEQ <= 6 ORDER BY CURR_SEQ OPEN curPos3 FETCH NEXT FROM curPos3 INTO @pos3 WHILE @@FETCH_STATUS = 0 BEGIN DECLARE curPos4 CURSOR FAST_FORWARD FOR SELECT WKLD_ID FROM TSA_HS_SEQ WHERE WKLD_ID NOT IN (@pos1,@pos2,@pos3) AND CURR_SEQ <= 6 ORDER BY CURR_SEQ OPEN curPos4 FETCH NEXT FROM curPos4 INTO @pos4 WHILE @@FETCH_STATUS = 0 BEGIN DECLARE curPos5 CURSOR FAST_FORWARD FOR SELECT WKLD_ID FROM TSA_HS_SEQ WHERE WKLD_ID NOT IN (@pos1,@pos2,@pos3,@pos4) AND CURR_SEQ <= 6 ORDER BY CURR_SEQ OPEN curPos5 FETCH NEXT FROM curPos5 INTO @pos5 WHILE @@FETCH_STATUS = 0 BEGIN DECLARE curPos6 CURSOR FAST_FORWARD FOR SELECT WKLD_ID FROM TSA_HS_SEQ WHERE WKLD_ID NOT IN (@pos1,@pos2,@pos3,@pos4,@pos5) AND CURR_SEQ <= 6 ORDER BY CURR_SEQ OPEN curPos6 FETCH NEXT FROM curPos6 INTO @pos6 WHILE @@FETCH_STATUS = 0 BEGIN BEGIN TRAN t1 INSERT INTO TSA_HS_COMB2 (COMB_ID, WKLD_ID, WKLD_SEQ) VALUES (@combID, @pos1, 1) INSERT INTO TSA_HS_COMB2 (COMB_ID, WKLD_ID, WKLD_SEQ) VALUES (@combID, @pos2, 2) INSERT INTO TSA_HS_COMB2 (COMB_ID, WKLD_ID, WKLD_SEQ) VALUES (@combID, @pos3, 3) INSERT INTO TSA_HS_COMB2 (COMB_ID, WKLD_ID, WKLD_SEQ) VALUES (@combID, @pos4, 4) INSERT INTO TSA_HS_COMB2 (COMB_ID, WKLD_ID, WKLD_SEQ) VALUES (@combID, @pos5, 5) INSERT INTO TSA_HS_COMB2 (COMB_ID, WKLD_ID, WKLD_SEQ) VALUES (@combID, @pos6, 6) COMMIT TRAN t1 SET @combID = @combID + 1 FETCH NEXT FROM curPos6 INTO @pos6 END CLOSE curPos6 DEALLOCATE curPos6 FETCH NEXT FROM curPos5 INTO @pos5 END CLOSE curPos5 DEALLOCATE curPos5 FETCH NEXT FROM curPos4 INTO @pos4 END CLOSE curPos4 DEALLOCATE curPos4 FETCH NEXT FROM curPos3 INTO @pos3 END CLOSE curPos3 DEALLOCATE curPos3 FETCH NEXT FROM curPos2 INTO @pos2 END CLOSE curPos2 DEALLOCATE curPos2 FETCH NEXT FROM curPos1 INTO @pos1 END CLOSE curPos1 DEALLOCATE curPos1``` If anybuddy's got any bright ideas on how to retire these cursors, I would love to hear it. Oh ya, AFAIK, the explicit transactions I added don't do a damn thing as far as imrpoving performance. Thanks again, Carl
 Brett Kaiser Window Washer Join Date: Nov 2002 Location: Jersey Posts: 10,322
 sort of has the homeworky feel to it.... If this is for a real business application, what's it for? __________________ Brett 8-) It's a Great Day for America everybody! dbforums Yak CorralRadio 'Rita dbForums Member List I'm Good Once as I ever was The physical order of data in a database has no meaning.
 blindman World Class Flame Warrior Join Date: Jun 2003 Location: Ohio Posts: 12,561
 Not exactly sure what you want. True factorial, or permutations of any (up to?) six values? Factorials are easy if you create a table of sequential values: Code: ```declare @N int set @N = 6 declare @Result int set @Result = 1 select @Result = @Result * (SeqValue + 1) from SequentialNumbers where SeqValue < @N select @Result``` __________________ If it's not practically useful, then it's practically useless. blindman www.chess.com: "sqlblindman" www.LobsterShot.blogspot.com
 carlmal Registered User Join Date: Jul 2004 Location: Edmonton, Canada Posts: 72
 Ya, it's a business app. It optimzes workload sequencing, answers the question "What do I do next?" It tries all 720 permutations, giving each a score. We simply pick the one with the highest score and earliest completion time. Carl
 Pat Phelan Resident Curmudgeon Join Date: Feb 2004 Location: In front of the computer Posts: 14,815
 The set based solution times at around 100 ms on my laptop. I'll give you a hint: five joins, and NOT IN. I'm just curious though, because this does sound a lot like homework to me too. -PatP
 Pat Phelan Resident Curmudgeon Join Date: Feb 2004 Location: In front of the computer Posts: 14,815
 Darn! I should have refreshed the page! Ok, I used: Code: ```DECLARE @dStart DATETIME SET @dStart = GetDate() CREATE TABLE #permutations ( id INT NOT NULL CONSTRAINT XPKpermutations PRIMARY KEY (id) ) INSERT INTO #permutations (id) SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 SELECT p1.id, p2.id, p3.id, p4.id, p5.id, p6.id FROM #permutations AS p1 JOIN #permutations AS p2 ON (p2.id NOT IN (p1.id)) JOIN #permutations AS p3 ON (p3.id NOT IN (p1.id, p2.id)) JOIN #permutations AS p4 ON (p4.id NOT IN (p1.id, p2.id, p3.id)) JOIN #permutations AS p5 ON (p5.id NOT IN (p1.id, p2.id, p3.id, p4.id)) JOIN #permutations AS p6 ON (p6.id NOT IN (p1.id, p2.id, p3.id, p4.id, p5.id)) ORDER BY 1, 2, 3, 4, 5, 6 DROP TABLE #permutations SELECT DateDiff(ms, @dStart, GetDate())``` -PatP
 carlmal Registered User Join Date: Jul 2004 Location: Edmonton, Canada Posts: 72
I need all permutations of the 6 values, without any of the values being repeated, which is 720 combinations (6 factorial).

I didn't mean to complicate by mentioning factorials, I did it to clarify that a value can only appear once in the combination.

Quote:
 Originally Posted by blindman Not exactly sure what you want. True factorial, or permutations of any (up to?) six values?
 carlmal Registered User Join Date: Jul 2004 Location: Edmonton, Canada Posts: 72
Geez yer gud.
Thanks Pat.
Carl
Quote:
 Originally Posted by Pat Phelan The set based solution times at around 100 ms on my laptop. I'll give you a hint: five joins, and NOT IN. I'm just curious though, because this does sound a lot like homework to me too. -PatP
 carlmal Registered User Join Date: Jul 2004 Location: Edmonton, Canada Posts: 72
 Mine has a COMB_ID field which tells you which of the 720 combintaions you're dealing with. How would you add a field with the values 1-720? Actually this would allow me to ditch a lot of my cursors, as many of them are simply to get an ordinal number for the record. Thanks again, Carl
 Pat Phelan Resident Curmudgeon Join Date: Feb 2004 Location: In front of the computer Posts: 14,815
 Ok, I'm gonna cheat on this one because I'm lazy and time constrained, but: Code: ```DECLARE @dStart DATETIME SET @dStart = GetDate() CREATE TABLE #permutations ( id INT NOT NULL CONSTRAINT XPKpermutations PRIMARY KEY (id) ) INSERT INTO #permutations (id) SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 CREATE TABLE #numberem ( id INT IDENTITY , i1 INT NOT NULL , i2 INT NOT NULL , i3 INT NOT NULL , i4 INT NOT NULL , i5 INT NOT NULL , i6 INT NOT NULL ) INSERT INTO #numberem (i1, i2, i3, i4, i5, i6) SELECT p1.id, p2.id, p3.id, p4.id, p5.id, p6.id FROM #permutations AS p1 JOIN #permutations AS p2 ON (p2.id NOT IN (p1.id)) JOIN #permutations AS p3 ON (p3.id NOT IN (p1.id, p2.id)) JOIN #permutations AS p4 ON (p4.id NOT IN (p1.id, p2.id, p3.id)) JOIN #permutations AS p5 ON (p5.id NOT IN (p1.id, p2.id, p3.id, p4.id)) JOIN #permutations AS p6 ON (p6.id NOT IN (p1.id, p2.id, p3.id, p4.id, p5.id)) ORDER BY 1, 2, 3, 4, 5, 6 SELECT * FROM #numberem DROP TABLE #numberem DROP TABLE #permutations SELECT DateDiff(ms, @dStart, GetDate())``` ...and it still runs in 120 ms on my laptop! Note that there are more efficient ways to do this from an execution perspective, but I don't have the time to code them. For less than a million rows, the difference is really trivial. -PatP