在SQL Server中生成排列的最优雅方法 [英] The most elegant way to generate permutations in SQL server

问题描述

给出下表:

Index | Element
---------------
  1   |    A
  2   |    B
  3   |    C
  4   |    D

我们想使用元素生成所有可能的排列(无重复). 最终结果(跳过一些行)将如下所示:

We want to generate all the possible permutations (without repetitions) using the elements. the final result (skipping some rows) will look like this:

  Results
----------
   ABCD
   ABDC
   ACBD
   ACDB
   ADAC
   ADCA

   ...

   DABC
   DACB
   DBCA
   DBAC
   DCAB
   DCBA

  (24 Rows)

您将如何做?

推荐答案

在发表了一些可能是刻板的评论之后，这个问题整夜困扰着我，最终我想出了以下基于集合的方法.我相信它绝对可以说是优雅"，但后来我也认为它可以说是有点笨".您打了电话.

After making some perhaps snarky comments, this problem stuck in my brain all evening, and I eventually came up with the following set-based approach. I believe it definitely qualifies as "elegant", but then I also think it qualifies as "kinda dumb". You make the call.

首先，设置一些表:

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

通常的想法是:将新元素(例如"B")添加到任何字符串(例如"A")时，要捕获所有排列，您将添加B 到所有可能的位置(Ba，aB)，从而产生一组新的字符串.然后进行迭代:将新元素(C)添加到字符串中的每个位置 (对于所有字符串(Cba，bCa，baC)，AB变为Cab，aCb，abC)，并且您具有一组排列.遍历每个结果集 下一个字符，直到用完字符或资源为止. 10个元素是360万个排列，按照上述算法，大约为48MB，而14个(唯一)元素将达到870亿个排列和1.163 TB.

The general idea is: when adding a new element (say "B") to any string (say, "A"), to catch all permutations you would add B to all possible positions (Ba, aB), resulting in a new set of strings. Then iterate: Add a new element (C) to each position in a string (AB becomes Cab, aCb, abC), for all strings (Cba, bCa, baC), and you have the set of permutations. Iterate over each result set with the next character until you run out of characters... or resources. 10 elements is 3.6 million permutations, roughly 48MB with the above algorithm, and 14 (unique) elements would hit 87 billion permutations and 1.163 terabytes.

我相信它最终可能会扎入CTE中，但最终所有这些都是光荣的循环.逻辑 这样更清晰，我忍不住认为CTE执行计划将是一场噩梦.

I'm sure it could eventually be wedged into a CTE, but in the end all that would be is a glorified loop. The logic is clearer this way, and I can't help but think the CTE execution plan would be a nightmare.

这篇关于在SQL Server中生成排列的最优雅方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！