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.

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,
Carlsort of has the homeworky feel to it...

If this is for a real business application, what's it for?|||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:declare @.N int
set @.N = 6

declare @.Result int
set @.Result = 1

select @.Result = @.Result * (SeqValue + 1) from SequentialNumbers where SeqValue < @.N

select @.Result|||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|||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|||Darn! I should have refreshed the page! Ok, I used: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|||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.

Not exactly sure what you want. True factorial, or permutations of any (up to?) six values?|||Geez yer gud.
Thanks Pat.
Carl
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|||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|||Ok, I'm gonna cheat on this one because I'm lazy and time constrained, but: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|||Sweet, 200mS over the wire from Montreal. Profuse gratitude, this is one I can reuse lots.