SQLServerで順列を生成する最も洗練された方法

恐らく卑劣なコメントをした後、この問題は一晩中私の頭に残っていました、そして私は最終的に次のセットベースのアプローチを思いつきました。間違いなく「エレガント」と言えると思いますが、それなら「ちょっとばかげている」とも思います。電話をかけます。

まず、いくつかのテーブルを設定します：

--  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
 )

ルーチンは次のとおりです：

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

一般的な考え方は次のとおりです。任意の文字列（たとえば「A」）に新しい要素（たとえば「B」）を追加する場合、すべての順列をキャッチするには、すべての可能な位置（Ba、aB）にBを追加し、新しいセットを作成します。文字列。次に繰り返します。すべての文字列（Cba、bCa、baC）について、文字列の各位置に新しい要素（C）を追加します（ABはCab、aCb、abCになります）。これで一連の順列ができます。文字またはリソースがなくなるまで、次の文字で各結果セットを繰り返します。 10個の要素は360万個の順列であり、上記のアルゴリズムでは約48MBであり、14個の（一意の）要素は870億個の順列と1.163テラバイトに達します。

最終的にはCTEに組み込まれる可能性があると確信していますが、最終的には、栄光のループになります。このように論理はより明確になり、CTE実行計画は悪夢になると思わざるを得ません。