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.

 
Go Back  dBforums > Database Server Software > Microsoft SQL Server > Factorial Permutations, Without a Cursor?

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1 (permalink)  
Old
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
Reply With Quote
  #2 (permalink)  
Old
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.
Reply With Quote
  #3 (permalink)  
Old
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
Reply With Quote
  #4 (permalink)  
Old
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
Reply With Quote
  #5 (permalink)  
Old
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
Reply With Quote
  #6 (permalink)  
Old
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
Reply With Quote
  #7 (permalink)  
Old
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?
Reply With Quote
  #8 (permalink)  
Old
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
Reply With Quote
  #9 (permalink)  
Old
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
Reply With Quote
  #10 (permalink)  
Old
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
Reply With Quote
  #11 (permalink)  
Old
Registered User
 
Join Date: Jul 2004
Location: Edmonton, Canada
Posts: 72
Sweet, 200mS over the wire from Montreal. Profuse gratitude, this is one I can reuse lots.
Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On