Results 1 to 11 of 11
  1. #1
    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

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

  3. #3
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,566
    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

  4. #4
    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

  5. #5
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    14,910
    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. #6
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    14,910
    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. #7
    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?

  8. #8
    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

  9. #9
    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

  10. #10
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    14,910
    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. #11
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •