복붙노트

[SQL] SQL 서버의 순열을 생성하는 가장 우아한 방법

SQL

SQL 서버의 순열을 생성하는 가장 우아한 방법

다음 표는 주어진 :

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

우리는 요소를 사용하여 (반복없이) 모든 가능한 순열을 생성합니다. 최종 결과는 (일부 행을 건너 뛰는)과 같이 표시됩니다 :

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

   ...

   DABC
   DACB
   DBCA
   DBAC
   DCAB
   DCBA

  (24 Rows)

당신은 어떻게 할 것인가?

해결법

  1. ==============================

    1.일부 아마도 snarky 의견을 한 후,이 문제는 저녁 내내 내 머리에 갇혀, 나는 결국 다음 세트 기반의 접근 방식 함께했다. 나는 확실히 "우아한"자격 생각하지만, 그때는 또한 "좀 바보"자격 생각합니다. 당신은 전화를 걸.

    일부 아마도 snarky 의견을 한 후,이 문제는 저녁 내내 내 머리에 갇혀, 나는 결국 다음 세트 기반의 접근 방식 함께했다. 나는 확실히 "우아한"자격 생각하지만, 그때는 또한 "좀 바보"자격 생각합니다. 당신은 전화를 걸.

    첫째, 일부 테이블을 설정 :

    --  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를 추가 할 수있는 모든 순열을 잡기 위해 어떤 문자열 ( "B"를 말한다) 문자열의 새로운 발생 가능한 모든 위치들 (BA, AB)에 관한 것이다. 그 다음으로 반복은 : 문자열의 각 위치에 새로운 요소 (C)를 추가 모든 문자열 (CBA, BCA, BAC)을 위해, (AB는 택시, ACB, ABC가된다), 당신은 순열의 집합을 가지고있다. 각 결과 세트 이상 반복 처리 다음 문자는 문자 ... 또는 자원을 소모 할 때까지. 10 개 요소는 360 만 순열, 위의 알고리즘 대략 48메가바이트, 14 (독특한) 요소 87000000000 순열과 1.163 테라 바이트를 칠 것입니다.

    나는 확실히 그것은 결국 CTE에 쐐기로 고정 할 수있어, 그러나 결국이 될 것이라고 모두가 영광 루프입니다. 논리 분명이 방법이며, 내가 도움이되지 수 있지만 CTE 실행 계획은 악몽이 될 것이라고 생각합니다.

  2. ==============================

    2.

    DECLARE @s VARCHAR(5);
SET @s = 'ABCDE';

WITH Subsets AS (
SELECT CAST(SUBSTRING(@s, Number, 1) AS VARCHAR(5)) AS Token,
CAST('.'+CAST(Number AS CHAR(1))+'.' AS VARCHAR(11)) AS Permutation,
CAST(1 AS INT) AS Iteration
FROM dbo.Numbers WHERE Number BETWEEN 1 AND 5
UNION ALL
SELECT CAST(Token+SUBSTRING(@s, Number, 1) AS VARCHAR(5)) AS Token,
CAST(Permutation+CAST(Number AS CHAR(1))+'.' AS VARCHAR(11)) AS
Permutation,
s.Iteration + 1 AS Iteration
FROM Subsets s JOIN dbo.Numbers n ON s.Permutation NOT LIKE
'%.'+CAST(Number AS CHAR(1))+'.%' AND s.Iteration < 5 AND Number
BETWEEN 1 AND 5
--AND s.Iteration = (SELECT MAX(Iteration) FROM Subsets)
)
SELECT * FROM Subsets
WHERE Iteration = 5
ORDER BY Permutation

Token Permutation Iteration
----- ----------- -----------
ABCDE .1.2.3.4.5. 5
ABCED .1.2.3.5.4. 5
ABDCE .1.2.4.3.5. 5
(snip)
EDBCA .5.4.2.3.1. 5
EDCAB .5.4.3.1.2. 5
EDCBA .5.4.3.2.1. 5

    첫 번째는 전에 여기 잠시 게시

    그러나, 같은 C #이나 C ++와 같은 더 나은 언어로 그것을 할 더 좋을 것이다.

  3. ==============================

    3.당신이 자신에게 테이블에 다른 열을 지렛대 수 있다면 그냥 SQL을 사용하여 임의의 코드없이, 당신은 그것을 할 수 있습니다. 분명히 당신은 각각의 값에 대해 하나 개의 조인 된 테이블이 교체 된해야 할 필요가있다.

    당신이 자신에게 테이블에 다른 열을 지렛대 수 있다면 그냥 SQL을 사용하여 임의의 코드없이, 당신은 그것을 할 수 있습니다. 분명히 당신은 각각의 값에 대해 하나 개의 조인 된 테이블이 교체 된해야 할 필요가있다.

    with llb as (
  select 'A' as col,1 as cnt union 
  select 'B' as col,3 as cnt union 
  select 'C' as col,9 as cnt union 
  select 'D' as col,27 as cnt
) 
select a1.col,a2.col,a3.col,a4.col
from llb a1
cross join llb a2
cross join llb a3
cross join llb a4
where a1.cnt + a2.cnt + a3.cnt + a4.cnt = 40
  4. ==============================

    4.나는 제대로 직교 제품 N X N X N X N, 다음 필터링 원치 않는 물건을 지은 이해하고 있습니까? 대안은 N까지의 모든 숫자를 생성하는 것입니다! 다음 요소 인코딩 통해 그들을 매핑 할 수 계승 시스템을 사용.

    나는 제대로 직교 제품 N X N X N X N, 다음 필터링 원치 않는 물건을 지은 이해하고 있습니까? 대안은 N까지의 모든 숫자를 생성하는 것입니다! 다음 요소 인코딩 통해 그들을 매핑 할 수 계승 시스템을 사용.

  5. ==============================

    5.재귀 CTE보다 간단 :

    재귀 CTE보다 간단 :

    declare @Number Table( Element varchar(MAX), Id varchar(MAX) )
Insert Into @Number Values ( 'A', '01')
Insert Into @Number Values ( 'B', '02')
Insert Into @Number Values ( 'C', '03')
Insert Into @Number Values ( 'D', '04')

select a.Element, b.Element, c.Element, d.Element
from @Number a
join @Number b on b.Element not in (a.Element)
join @Number c on c.Element not in (a.Element, b.Element)
join @Number d on d.Element not in (a.Element, b.Element, c.Element)
order by 1, 2, 3, 4

    임의의 수의 요소를 들어, 스크립트를 아웃 :

    if object_id('tempdb..#number') is not null drop table #number
create table #number (Element char(1), Id int, Alias as '_'+convert(varchar,Id))
insert #number values ('A', 1)
insert #number values ('B', 2)
insert #number values ('C', 3)
insert #number values ('D', 4)
insert #number values ('E', 5)

declare @sql nvarchar(max)
set @sql = '
select '+stuff((
  select char(13)+char(10)+'+'+Alias+'.Element'
  from #number order by Id for xml path (''), type
  ).value('.','NVARCHAR(MAX)'),3,1,' ')

set @sql += '
from #number '+(select top 1 Alias from #number order by Id)

set @sql += (
  select char(13)+char(10)+'join #number '+Alias+' on '+Alias+'.Id not in ('
    +stuff((
      select ', '+Alias+'.Id'
      from #number b where a.Id > b.Id
      order by Id for xml path ('')
      ),1,2,'')
    + ')'
  from #number a where Id > (select min(Id) from #number)
  order by Element for xml path (''), type
  ).value('.','NVARCHAR(MAX)')

set @sql += '
order by 1'

print @sql
exec (@sql)

    이를 생성하려면 :

    select 
 _1.Element
+_2.Element
+_3.Element
+_4.Element
+_5.Element
from #number _1
join #number _2 on _2.Id not in (_1.Id)
join #number _3 on _3.Id not in (_1.Id, _2.Id)
join #number _4 on _4.Id not in (_1.Id, _2.Id, _3.Id)
join #number _5 on _5.Id not in (_1.Id, _2.Id, _3.Id, _4.Id)
order by 1
  6. ==============================

    6.이 방법은 올바른 행을 선택 바이너리 마스크를 사용합니다 :

    이 방법은 올바른 행을 선택 바이너리 마스크를 사용합니다 :

    ;with src(t,n,p) as (
select element, index, power(2,index-1)
from table
)
select s1.t+s2.t+s3.t+s4.t
from src s1, src s2, src s3, src s4
where s1.p+s2.p+s3.p+s4.p=power(2,4)-1

    내 원래 게시물 :

    declare @t varchar(4) = 'ABCD'

;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
from src s1, src s2, src s3, src s4
where s1.p+s2.p+s3.p+s4.p=power(2,len(@t))-1

    이 출몰하는 이러한 문제 둘 중 하나입니다. 나는 내 원래의 대답의 단순함을 좋아하지만 난 여전히 올바른 사람을 선택 모든 가능한 솔루션을 구축 한이 문제가 발생했습니다. 하나는 더이 과정을보다 효율적으로 만 정확 솔루션이 답을 산출 구축하여 만들려고. 그 문자가 문자열에 존재하지 않은 경우에만 문자열에 문자를 추가합니다. PATINDEX는 CTE 솔루션을위한 완벽한 동반자처럼 보였다. 여기있어.

    declare @t varchar(10) = 'ABCDEFGHIJ'

;with s(t,n) as (
select substring(@t,1,1),1
union all
select substring(@t,n+1,1),n+1
from s where n<len(@t)
)
,j(t) as (
select cast(t as varchar(10)) from s
union all
select cast(j.t+s.t as varchar(10))
from j,s where patindex('%'+s.t+'%',j.t)=0
)
select t from j where len(t)=len(@t)

    나는 삼분 2 초에 모두 360 만 개 솔루션을 구축 할 수 있었다. 희망이 솔루션은 처음이 아니다해서 놓친되지 않습니다.

  7. ==============================

    7.재귀 CTE를 사용하여 현재 솔루션입니다.

    재귀 CTE를 사용하여 현재 솔루션입니다.

    -- The base elements
Declare @Number Table( Element varchar(MAX), Id varchar(MAX) )
Insert Into @Number Values ( 'A', '01')
Insert Into @Number Values ( 'B', '02')
Insert Into @Number Values ( 'C', '03')
Insert Into @Number Values ( 'D', '04')

-- Number of elements
Declare @ElementsNumber int
Select  @ElementsNumber = COUNT(*)
From    @Number;



-- Permute!
With Permutations(   Permutation,   -- The permutation generated
                     Ids,            -- Which elements where used in the permutation
                     Depth )         -- The permutation length
As
(
    Select  Element,
            Id + ';',
            Depth = 1
    From    @Number
    Union All
    Select  Permutation + ' ' + Element,
            Ids + Id + ';',
            Depth = Depth + 1
    From    Permutations,
            @Number
    Where   Depth < @ElementsNumber And -- Generate only the required permutation number
            Ids Not like '%' + Id + ';%' -- Do not repeat elements in the permutation (this is the reason why we need the 'Ids' column) 
)
Select  Permutation
From    Permutations
Where   Depth = @ElementsNumber
  8. ==============================

    8.가정 테이블이 요소의 이름과 4 개 행이되고,이는 간단하다 :

    가정 테이블이 요소의 이름과 4 개 행이되고,이는 간단하다 :

    select e1.Element + e2.Element + e3.Element + e4.Element
from Elements e1
    join Elements e2 on e2.Element != e1.Element 
    join Elements e3 on e3.Element != e2.Element AND e3.Element != e1.Element 
    join Elements e4 on e4.Element != e3.Element AND e4.Element != e2.Element AND e4.Element != e1.Element
  9. ==============================

    9.방법 내 SQL 기술에 너무 많이 녹,하지만 난 비슷한 문제에 대해 다른 압정을했다 및 가치 공유를 생각했다.

    방법 내 SQL 기술에 너무 많이 녹,하지만 난 비슷한 문제에 대해 다른 압정을했다 및 가치 공유를 생각했다.

    Table1 - X strings in a single field Uno
Table2 - Y strings in a single field Dos

(SELECT Uno, Dos
FROM Table1
CROSS JOIN Table2 ON 1=1)
    UNION
(SELECT  Dos, Uno
FROM Table1
CROSS JOIN Table2 ON 1=1)

    추가 CROSS 3 개 테이블을 가입하기 위해 동일한 원리

    (SELECT  Tres, Uno, Dos
FROM Table1
CROSS JOIN Table2 ON 1=1
    CROSS JOIN Table3 ON 1=1)

    걸리는 있지만 6은 노동 조합의 집합을 교차 가입 할 수 있습니다.

  10. ==============================

    10.--Hopefully이 빠른 솔루션입니다, 단지 값이 #X에 들어가는 변경

    --Hopefully이 빠른 솔루션입니다, 단지 값이 #X에 들어가는 변경

    IF OBJECT_ID('tempdb.dbo.#X', 'U') IS NOT NULL  DROP TABLE #X; CREATE table #X([Opt] [nvarchar](10) NOT NULL)
Insert into #X values('a'),('b'),('c'),('d')
declare @pSQL NVarChar(max)='select * from #X X1 ', @pN int =(select count(*) from #X), @pC int = 0;
while @pC<@pN begin
if @pC>0 set  @pSQL = concat(@pSQL,' cross join #X X', @pC+1);
set @pC = @pC +1;
end
execute(@pSQL)

    단일 - 또는 열의 결과로서

    IF OBJECT_ID('tempdb.dbo.#X', 'U') IS NOT NULL  DROP TABLE #X; CREATE table #X([Opt] [nvarchar](10) NOT NULL)
Insert into #X values('a'),('b'),('c'),('d')
declare @pSQL NVarChar(max)=' as R from #X X1 ',@pSelect NVarChar(Max)=' ',@pJoin NVarChar(Max)='', @pN int =(select count(*) from #X), @pC int = 0;
while @pC<@pN begin
if @pC>0 set  @pJoin = concat(@pJoin ,' cross join #X X', @pC+1) set @pSelect =  concat(@pSelect ,'+ X', @pC+1,'.Opt ')
set @pC = @pC +1;
end
set @pSQL = concat ('select X1.Opt', @pSelect,@pSQL ,@pJoin)
exec(@pSQL)

    11. from https://stackoverflow.com/questions/3621494/the-most-elegant-way-to-generate-permutations-in-sql-server by cc-by-sa and MIT license

'SQL' 카테고리의 다른 글

[SQL] PBKDF2의 SQL 구현이 있습니까?  (0) 2020.05.03
[SQL] 두 개의 열을 사용하여 데이터의 피벗  (0) 2020.05.03
[SQL] 어떻게 CASE 표현식은 ELSE 절에 도달 하는가?  (0) 2020.05.03
[SQL] 어떻게 여러 테이블에 데이터 집합을 채우기 위해?  (0) 2020.05.03
[SQL] JDBC에서 누락 dll을  (0) 2020.05.03
,

티스토리툴바