Det mest eleganta sättet att generera permutationer i SQL-server

Efter att ha gjort några kanske snåriga kommentarer fastnade det här problemet i min hjärna hela kvällen, och jag kom till slut på följande uppsättningsbaserade tillvägagångssätt. Jag tror definitivt att den kvalificerar sig som "elegant", men sedan tycker jag också att den kvalificeras som "ganska dum". Du ringer.

Skapa först några tabeller:

--  For testing purposes
DROP TABLE Source
DROP TABLE Numbers
DROP TABLE Results


--  Add as many rows as need be processed--though note that you get N! (number of rows, factorial) results,
--  and that gets big fast. The Identity column must start at 1, or the algorithm will have to be adjusted.
--  Element could be more than char(1), though the algorithm would have to be adjusted again, and each element
--  must be the same length.
CREATE TABLE Source
 (
   SourceId  int      not null  identity(1,1)
  ,Element   char(1)  not null
 )

INSERT Source (Element) values ('A')
INSERT Source (Element) values ('B')
INSERT Source (Element) values ('C')
INSERT Source (Element) values ('D')
--INSERT Source (Element) values ('E')
--INSERT Source (Element) values ('F')


--  This is a standard Tally table (or "table of numbers")
--  It only needs to be as long as there are elements in table Source
CREATE TABLE Numbers (Number int not null)
INSERT Numbers (Number) values (1)
INSERT Numbers (Number) values (2)
INSERT Numbers (Number) values (3)
INSERT Numbers (Number) values (4)
INSERT Numbers (Number) values (5)
INSERT Numbers (Number) values (6)
INSERT Numbers (Number) values (7)
INSERT Numbers (Number) values (8)
INSERT Numbers (Number) values (9)
INSERT Numbers (Number) values (10)


--  Results are iteratively built here. This could be a temp table. An index on "Length" might make runs
--  faster for large sets.  Combo must be at least as long as there are characters to be permuted.
CREATE TABLE Results
 (
   Combo   varchar(10)  not null
  ,Length  int          not null
 )

Här är rutinen:

SET NOCOUNT on

DECLARE
  @Loop     int
 ,@MaxLoop  int


--  How many elements there are to process
SELECT @MaxLoop = max(SourceId)
 from Source


--  Initialize first value
TRUNCATE TABLE Results
INSERT Results (Combo, Length)
 select Element, 1
  from Source
  where SourceId = 1

SET @Loop = 2

--  Iterate to add each element after the first
WHILE @Loop <= @MaxLoop
 BEGIN

    --  See comments below. Note that the "distinct" remove duplicates, if a given value
    --  is to be included more than once
    INSERT Results (Combo, Length)
     select distinct
        left(re.Combo, @Loop - nm.Number)
        + so.Element
        + right(re.Combo, nm.Number - 1)
       ,@Loop
      from Results re
       inner join Numbers nm
        on nm.Number <= @Loop
       inner join Source so
        on so.SourceId = @Loop
      where re.Length = @Loop - 1

    --  For performance, add this in if sets will be large
    --DELETE Results
    -- where Length <> @Loop

    SET @Loop = @Loop + 1
 END

--  Show results
SELECT *
 from Results
 where Length = @MaxLoop
 order by Combo

Den allmänna idén är:när du lägger till ett nytt element (säg "B") till en sträng (säg, "A"), för att fånga alla permutationer skulle du lägga till B till alla möjliga positioner (Ba, aB), vilket resulterar i en ny uppsättning av strängar. Iterera sedan:Lägg till ett nytt element (C) till varje position i en sträng (AB blir Cab, aCb, abC), för alla strängar (Cba, bCa, baC), och du har uppsättningen av permutationer. Iterera över varje resultatuppsättning med nästa tecken tills du får slut på tecken... eller resurser. 10 element är 3,6 miljoner permutationer, ungefär 48 MB med ovanstående algoritm, och 14 (unika) element skulle träffa 87 miljarder permutationer och 1,163 terabyte.

Jag är säker på att det så småningom skulle kunna kilas in i en CTE, men i slutändan skulle det bara vara en glorifierad loop. Logiken är tydligare på det här sättet, och jag kan inte låta bli att tro att CTE:s genomförandeplan skulle vara en mardröm.