Cách thanh lịch nhất để tạo hoán vị trong máy chủ SQL

Sau khi đưa ra một số nhận xét có lẽ khó hiểu, vấn đề này đã mắc kẹt trong não tôi cả buổi tối, và cuối cùng tôi đã nghĩ ra cách tiếp cận dựa trên thiết lập sau đây. Tôi tin rằng nó chắc chắn đủ tiêu chuẩn là "thanh lịch", nhưng sau đó tôi cũng nghĩ rằng nó đủ tiêu chuẩn là "hơi đần độn". Bạn thực hiện cuộc gọi.

Đầu tiên, hãy thiết lập một số bảng:

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

Đây là quy trình:

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

Ý tưởng chung là:khi thêm một phần tử mới (giả sử "B") vào bất kỳ chuỗi nào (giả sử, "A"), để bắt tất cả các hoán vị, bạn sẽ thêm B vào tất cả các vị trí có thể (Ba, aB), dẫn đến một tập hợp mới dây. Sau đó lặp lại:Thêm một phần tử mới (C) vào mỗi vị trí trong một chuỗi (AB trở thành Cab, aCb, abC), cho tất cả các chuỗi (Cba, bCa, baC) và bạn có tập hợp các hoán vị. Lặp lại từng tập kết quả với ký tự tiếp theo cho đến khi bạn dùng hết ký tự ... hoặc tài nguyên. 10 phần tử là 3,6 triệu hoán vị, khoảng 48MB với thuật toán trên và 14 phần tử (duy nhất) sẽ đạt 87 tỷ hoán vị và 1,163 terabyte.

Tôi chắc chắn rằng cuối cùng nó có thể được đưa vào một CTE, nhưng cuối cùng tất cả những gì sẽ là một vòng lặp được tôn vinh. Theo cách này, logic rõ ràng hơn và tôi không thể không nghĩ kế hoạch thực thi CTE sẽ là một cơn ác mộng.