Generating Permutations in T-SQL

  • Eli Leiba

    SSC-Addicted

    Points: 461

    Comments posted to this topic are about the content posted at http://www.sqlservercentral.com/columnists/eleiba/generatingpermutationsintsql.asp

  • John Scarborough

    Ten Centuries

    Points: 1104

    Nice article! I really had to "think" my way through this one, but its likely to be very useful.

    John Scarborough
    MCDBA, MCSA

  • HelloFOFO

    Old Hand

    Points: 349

    I think it is better to limit the input parameter @n <= 10.

    I modify this proc in my SQL 2000 Query Analyzer

    just change the length of all parameters such as @sqlStmt,@base etc. to

    5000

    Then,I used 11 as input parameter and the Query Analyzer return an error:

    can't generate query plan......

    But I didn't try 10......

  • Michael Wang

    SSC Veteran

    Points: 203

    I see nothing wrong with procedural code if implemeneted properly.  The original code has the problem of being too complex and is also limited in scope.  I ran it up to 7, beyond which my SQL2000 will not be able to generate a plan.  The procedure below is inspired by the original code but is drastically different: it handles large set really fast and dynamic SQL statement is short and recursive (use @debug = 1 to see it).

    To use it, you need to store your values in a table with a single column 'x'.  This procedure permutes r out of n.  Of course you need to make sure r<=n, and be aware that the result set could be substantial (n! / (n-r)! permutations).

    It may not be useful, but just for fun.

    Create Proc sp_permutate (@n smallint, @t varchar(8), @debug bit = 0)

    as

    begin

     set nocount on

     declare @sqlStmt varchar(4000), @delim varchar(2)

     declare @i int

     declare @j int

    if @debug = 1 set @delim = char(10) else set @delim = ''

    set @sqlStmt = 'SELECT x' + cast(@n as varchar(2)) + '=X from ' + @t + @delim

    set @i = @n -1

    while @i > 0

    Begin

     set @j = @n

     set @sqlStmt = 'SELECT x' + cast(@i as varchar(2)) + '=X, T.* from ' + @t +

     ' join (' + @delim + @sqlStmt + ') T on x<>x' + cast(@j as varchar(2))

     set @j = @j - 1

     while @j > @i

     Begin

      set @sqlStmt = @sqlStmt + ' and x<>x' + cast(@j as varchar(2))

      set @j = @j - 1

     End

     set @sqlStmt = @sqlStmt + @delim

     set @i = @i - 1

    End

     print @sqlStmt

     exec (@sqlStmt)

     set nocount off

    end

    go

     

  • Eli Leiba

    SSC-Addicted

    Points: 461

    SQL 2005 has CTE that can do the permutations more easy

    I coded for SQL-2000 ,

    If you use a phisical table and not a "memory table" like

    (select 1 union select 2 union ........)

    then the optimizer will crush for more than 10 join with the table

    to itself so memory derived tables must be used on this one

  • RyanRandall

    SSChampion

    Points: 13623

    Hi all,

    I wrote this for fun, and thought I'd share it here, since it's vaguely related. It's interesting mathematics (in that the method works) if nothing else.

    If you set @i below to your set size, then a list of all combinations of numbers is returned (as a varchar). e.g. @i = 3 gives:

    210

    201

    120

    021

    102

    012

    The timings on my pc are:

    Size  Seconds  Rows

    7     0        5040

    8     1        40320

    9     6        362880

    10    60       3628800

    --This SQL script is safe to run

    --Inputs

    DECLARE @i TINYINT

    SET @i = 7 --set size

    --Validation

    IF @i > 10 BEGIN PRINT 'i is too large' SET @i = 0 END

    --Declarations

    CREATE TABLE #t (n TINYINT, v VARCHAR(10))

    CREATE CLUSTERED INDEX #ix_t ON #t (n)

    DECLARE @n TABLE (i TINYINT) --numbers table

    DECLARE @Counter INT

    --Initialisations

    INSERT @n SELECT 0

    INSERT #t SELECT 0, '0 '

    SET @Counter = 1

    --Loop for each integer from 1 to @i-1

    WHILE @Counter <= @i - 1

    BEGIN

        INSERT @n SELECT @Counter

        INSERT #t SELECT @Counter, STUFF(v, i+1, 0, @Counter)

                  FROM #t, @n WHERE n = @Counter - 1

        SET @Counter = @Counter + 1

    END

    --Select results we're interested in

    SELECT v FROM #t WHERE n = @i - 1

    --Tidy up

    DROP TABLE #t

     

    Ryan Randall

    Solutions are easy. Understanding the problem, now, that's the hard part.

  • Dennis D. Allen

    Say Hey Kid

    Points: 689

    Just to toss my hat in the ring...

    create procedure dbo.usp_permutate

    @charset nvarchar(256) = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

    as

    set nocount on

    -- a set of all values in the charset

    create table #set ( k int, v nchar(1) )

    declare @i int, @C nvarchar(5)

    declare @select nvarchar(4000)

    declare @from nvarchar(4000)

    select

    @i = 1

    , @select = 's1.v '

    , @from = '#set s1 '

    insert into #set ( k, v ) values ( 1, substring(@charset, @i, 1) )

    while @i < len(@charset) begin

    set @i = @i + 1

    set @C = convert(nvarchar(5), @i)

    insert into #set ( k, v ) values ( 1, substring(@charset, @i, 1) )

    set @select = @select + '+ s' + @C + '.v '

    set @from = @from + 'join #set s' + @C + ' on s' + @C + '.k = s1.k '

    end

    -- output query

    exec( 'select ' + @select + 'as permutation from ' + @from + 'order by permutation' )

    -- clean up

    drop table #set

  • Frédéric BROUARD

    Old Hand

    Points: 309

    This calculus can be done in only one query

    (I think I am the first to demontsrate how to do that in one query only !) 😉

    -- lest's assume that this table containes all datas to be permuted :

    CREATE TABLE T_CMB (CMB_DATA VARCHAR(8))

    -- let's assume that the joker character ; (dot comma) is not used inside the data :

    INSERT INTO T_CMB VALUES ('ABC')

    INSERT INTO T_CMB VALUES ('DEF')

    INSERT INTO T_CMB VALUES ('GHI')

    -- the following query does the permutations

    WITH

    T_DATA AS

    (SELECT CMB_DATA, 1 AS COMBINAISON,

    ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE,

    COUNT(*) OVER() AS N

    FROM T_CMB),

    T_RECUR AS

    (SELECT CAST(CMB_DATA AS VARCHAR(max)) +';' AS CMB_DATA, COMBINAISON, ORDRE, N

    FROM T_DATA

    UNION ALL

    SELECT T1.CMB_DATA + ';' + T2.CMB_DATA, T2.COMBINAISON + 1, ROW_NUMBER() OVER(PARTITION BY T1.COMBINAISON ORDER BY T2.CMB_DATA) ORDRE, T1.N

    FROM T_DATA AS T1

    CROSS JOIN T_RECUR AS T2

    WHERE T2.COMBINAISON < T1.N

    -- this line must be delete if you want a repetitive permutation

    AND T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'

    ),

    T_COMBINE AS

    (SELECT CMB_DATA, ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE

    FROM T_RECUR

    WHERE COMBINAISON = N),

    T_N AS

    (SELECT 1 AS N

    UNION ALL

    SELECT N + 1

    FROM T_N

    WHERE N + 1 <= ALL (SELECT LEN(CMB_DATA)

    FROM T_COMBINE)),

    T_SOL AS

    (SELECT *, REVERSE(SUBSTRING(CMB_DATA, 1, N-1)) AS SOUS_CHAINE,

    REVERSE(SUBSTRING(REVERSE(SUBSTRING(CMB_DATA, 1, N-1)), 1,

    CASE

    WHEN CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1 = -1 THEN LEN(CMB_DATA)

    ELSE CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1

    END)) AS DATA

    FROM T_COMBINE

    INNER JOIN T_N

    ON SUBSTRING(CMB_DATA, N, 1) = ';')

    SELECT DATA AS CMB_DATA, ORDRE AS PERMUTATION

    FROM T_SOL

    CMB_DATA PERMUTATION

    ------------------------- --------------------

    ABC 1

    DEF 1

    GHI 1

    ABC 2

    GHI 2

    DEF 2

    DEF 3

    ABC 3

    GHI 3

    DEF 4

    GHI 4

    ABC 4

    GHI 5

    ABC 5

    DEF 5

    GHI 6

    DEF 6

    ABC 6

    If you want a permutation with repetitive datas, simply delete the 18e line :

    AND T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'

    You'll get :

    CMB_DATA PERMUTATION

    ----------------------- --------------------

    ABC 1

    ABC 1

    ABC 1

    ABC 2

    ABC 2

    DEF 2

    ABC 3

    ABC 3

    GHI 3

    ABC 4

    DEF 4

    ABC 4

    ABC 5

    DEF 5

    DEF 5

    ABC 6

    DEF 6

    GHI 6

    ABC 7

    GHI 7

    ABC 7

    ABC 8

    GHI 8

    DEF 8

    ABC 9

    GHI 9

    GHI 9

    DEF 10

    ABC 10

    ABC 10

    DEF 11

    ABC 11

    DEF 11

    DEF 12

    ABC 12

    GHI 12

    DEF 13

    DEF 13

    ABC 13

    DEF 14

    DEF 14

    DEF 14

    DEF 15

    DEF 15

    GHI 15

    DEF 16

    GHI 16

    ABC 16

    DEF 17

    GHI 17

    DEF 17

    DEF 18

    GHI 18

    GHI 18

    GHI 19

    ABC 19

    ABC 19

    GHI 20

    ABC 20

    DEF 20

    GHI 21

    ABC 21

    GHI 21

    GHI 22

    DEF 22

    ABC 22

    GHI 23

    DEF 23

    DEF 23

    GHI 24

    DEF 24

    GHI 24

    GHI 25

    GHI 25

    ABC 25

    GHI 26

    GHI 26

    DEF 26

    GHI 27

    GHI 27

    GHI 27

    The french version is on my blog :

    http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathema

    CU

    ---

    Frédéric BROUARD, Spécialiste modélisation, bases de données, optimisation, langage SQL.

    Le site sur le langage SQL et les S.G.B.D. relationnels : http://sqlpro.developpez.com/[/url]

    Expert SQL Server http://www.sqlspot.com : audit, optimisation, tuning, formation

    * * * * * Enseignant au CNAM PACA et à l'ISEN à Toulon * * * * *

  • RyanRandall

    SSChampion

    Points: 13623

    Frédéric BROUARD (1/8/2009) ...

    Here's something similar for comparison, making use of powers of 2 rather than LIKE, and XML rather than string manuipulation.

    --preparation

    IF OBJECT_ID('tempdb.dbo.#t1') IS NOT NULL DROP TABLE #t1

    GO

    --/

    --structure

    CREATE TABLE #t1 (x VARCHAR(MAX))

    --/

    --data

    INSERT INTO #t1 VALUES ('ABC')

    INSERT INTO #t1 VALUES ('DEF')

    INSERT INTO #t1 VALUES ('GHI')

    --/

    --parameters

    DECLARE @AllowDuplicates BIT

    SET @AllowDuplicates = 0

    --/

    --query

    ; WITH

    a AS (SELECT COUNT(*) AS cnt FROM #t1)

    , b AS (SELECT POWER(2, ROW_NUMBER() OVER(ORDER BY x)-1) AS marker, x FROM #t1)

    , c AS (SELECT marker, 1 as level, '<x>' + x + '</x>' AS x FROM b UNION ALL

    SELECT c.marker + b.marker, c.level + 1, c.x + '<x>' + b.x + '</x>'

    FROM b INNER JOIN c ON (@AllowDuplicates = 1 OR b.marker & c.marker = 0)

    WHERE c.level < (SELECT cnt FROM a))

    , d AS (SELECT ROW_NUMBER() OVER(ORDER BY x) as permutation, cast(x as xml) as xml

    FROM c WHERE level = (SELECT cnt FROM a))

    SELECT

    d.permutation,

    ROW_NUMBER() OVER(PARTITION BY d.permutation ORDER BY d.permutation) AS position,

    c.value('.', 'varchar(100)') AS value

    FROM d CROSS APPLY xml.nodes('//x') T(c)

    --/

    Ryan Randall

    Solutions are easy. Understanding the problem, now, that's the hard part.

  • Frédéric BROUARD

    Old Hand

    Points: 309

    Excellent.

    I must say that I have try with power of 2 but I do not find a correct answer. But I do not like to use of XML wich is rather out of SQL control.

    But your solution is quite more elegant.

    I have had no time to tune my fisrt one. But I think there is a more concise way to do that job !

    A + (wich me CU in french)

    PS : I posted yourt solution, rewrited in my french blog !

    http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathema

  • RyanRandall

    SSChampion

    Points: 13623

    Thanks Frédéric 🙂

    I dare say that's my first ever 'publication' in a foreign language - great stuff!

    Ryan Randall

    Solutions are easy. Understanding the problem, now, that's the hard part.

  • Frédéric BROUARD

    Old Hand

    Points: 309

    I hope it won't be the last !

    A +

  • paolosaurus

    SSC Journeyman

    Points: 82

    regarding the original query. It seems repetition of the characters is not allowed. This is therefore not a permutations calculator but is a combinations calculator.

  • kgresham

    SSC Enthusiast

    Points: 197

    This uses a binary mask to select the unique sets where one of each character are present. It runs in about 14 seconds.

    declare @t varchar(10) = 'ABCDEFGH'

    ;with src(t,n,p) as (

    select substring(@t,1,1),1,power(2,0)

    union all

    select substring(@t,n+1,1),n+1,power(2,n)

    from src

    where n < len(@t)

    )

    select s1.t+s2.t+s3.t+s4.t+s5.t+s6.t+s7.t+s8.t

    from src s1, src s2, src s3, src s4, src s5, src s6, src s7, src s8

    where s1.p+s2.p+s3.p+s4.p+s5.p+s6.p+s7.p+s8.p=power(2,len(@t))-1

  • Jeff Moden

    SSC Guru

    Points: 995703

    Frédéric BROUARD (1/8/2009)


    This calculus can be done in only one query

    (I think I am the first to demontsrate how to do that in one query only !) 😉

    -- lest's assume that this table containes all datas to be permuted :

    CREATE TABLE T_CMB (CMB_DATA VARCHAR(8))

    -- let's assume that the joker character ; (dot comma) is not used inside the data :

    INSERT INTO T_CMB VALUES ('ABC')

    INSERT INTO T_CMB VALUES ('DEF')

    INSERT INTO T_CMB VALUES ('GHI')

    -- the following query does the permutations

    WITH

    T_DATA AS

    (SELECT CMB_DATA, 1 AS COMBINAISON,

    ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE,

    COUNT(*) OVER() AS N

    FROM T_CMB),

    T_RECUR AS

    (SELECT CAST(CMB_DATA AS VARCHAR(max)) +';' AS CMB_DATA, COMBINAISON, ORDRE, N

    FROM T_DATA

    UNION ALL

    SELECT T1.CMB_DATA + ';' + T2.CMB_DATA, T2.COMBINAISON + 1, ROW_NUMBER() OVER(PARTITION BY T1.COMBINAISON ORDER BY T2.CMB_DATA) ORDRE, T1.N

    FROM T_DATA AS T1

    CROSS JOIN T_RECUR AS T2

    WHERE T2.COMBINAISON < T1.N

    -- this line must be delete if you want a repetitive permutation

    AND T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'

    ),

    T_COMBINE AS

    (SELECT CMB_DATA, ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE

    FROM T_RECUR

    WHERE COMBINAISON = N),

    T_N AS

    (SELECT 1 AS N

    UNION ALL

    SELECT N + 1

    FROM T_N

    WHERE N + 1 <= ALL (SELECT LEN(CMB_DATA)

    FROM T_COMBINE)),

    T_SOL AS

    (SELECT *, REVERSE(SUBSTRING(CMB_DATA, 1, N-1)) AS SOUS_CHAINE,

    REVERSE(SUBSTRING(REVERSE(SUBSTRING(CMB_DATA, 1, N-1)), 1,

    CASE

    WHEN CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1 = -1 THEN LEN(CMB_DATA)

    ELSE CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1

    END)) AS DATA

    FROM T_COMBINE

    INNER JOIN T_N

    ON SUBSTRING(CMB_DATA, N, 1) = ';')

    SELECT DATA AS CMB_DATA, ORDRE AS PERMUTATION

    FROM T_SOL

    CMB_DATA PERMUTATION

    ------------------------- --------------------

    ABC 1

    DEF 1

    GHI 1

    ABC 2

    GHI 2

    DEF 2

    DEF 3

    ABC 3

    GHI 3

    DEF 4

    GHI 4

    ABC 4

    GHI 5

    ABC 5

    DEF 5

    GHI 6

    DEF 6

    ABC 6

    If you want a permutation with repetitive datas, simply delete the 18e line :

    AND T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'

    You'll get :

    CMB_DATA PERMUTATION

    ----------------------- --------------------

    ABC 1

    ABC 1

    ABC 1

    ABC 2

    ABC 2

    DEF 2

    ABC 3

    ABC 3

    GHI 3

    ABC 4

    DEF 4

    ABC 4

    ABC 5

    DEF 5

    DEF 5

    ABC 6

    DEF 6

    GHI 6

    ABC 7

    GHI 7

    ABC 7

    ABC 8

    GHI 8

    DEF 8

    ABC 9

    GHI 9

    GHI 9

    DEF 10

    ABC 10

    ABC 10

    DEF 11

    ABC 11

    DEF 11

    DEF 12

    ABC 12

    GHI 12

    DEF 13

    DEF 13

    ABC 13

    DEF 14

    DEF 14

    DEF 14

    DEF 15

    DEF 15

    GHI 15

    DEF 16

    GHI 16

    ABC 16

    DEF 17

    GHI 17

    DEF 17

    DEF 18

    GHI 18

    GHI 18

    GHI 19

    ABC 19

    ABC 19

    GHI 20

    ABC 20

    DEF 20

    GHI 21

    ABC 21

    GHI 21

    GHI 22

    DEF 22

    ABC 22

    GHI 23

    DEF 23

    DEF 23

    GHI 24

    DEF 24

    GHI 24

    GHI 25

    GHI 25

    ABC 25

    GHI 26

    GHI 26

    DEF 26

    GHI 27

    GHI 27

    GHI 27

    The french version is on my blog :

    http://blog.developpez.com/sqlpro?title=calculs_de_tous_les_arrangements_mathema

    CU

    ---

    Frédéric BROUARD, Spécialiste modélisation, bases de données, optimisation, langage SQL.

    Le site sur le langage SQL et les S.G.B.D. relationnels : http://sqlpro.developpez.com/[/url]

    Expert SQL Server http://www.sqlspot.com : audit, optimisation, tuning, formation

    * * * * * Enseignant au CNAM PACA et à l'ISEN à Toulon * * * * *

    At a "9" count, you're also the first to get beat by the While loop by a factor of more than 30 even with discarded results enabled. 😉

    --Jeff Moden


    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
    "If you think its expensive to hire a professional to do the job, wait until you hire an amateur."--Red Adair
    "Change is inevitable... change for the better is not."

    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

Viewing 15 posts - 1 through 15 (of 16 total)

You must be logged in to reply to this topic. Login to reply