# Thread: Factorial Permutations, Without a Cursor?

1. Registered User
Join Date
Jul 2004
Location
Posts
72

## Unanswered: 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

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

3. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
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```

4. Registered User
Join Date
Jul 2004
Location
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

5. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
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

6. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
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

7. Registered User
Join Date
Jul 2004
Location
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.

Originally Posted by blindman
Not exactly sure what you want. True factorial, or permutations of any (up to?) six values?

8. Registered User
Join Date
Jul 2004
Location
Posts
72
Geez yer gud.
Thanks Pat.
Carl
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

9. Registered User
Join Date
Jul 2004
Location
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

10. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
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

11. Registered User
Join Date
Jul 2004
Location