Самый элегантный способ генерации перестановок на 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
Сделав некоторые, возможно, злобные комментарии, эта проблема застряла в моем мозгу весь вечер, и в итоге я придумал следующий подход, основанный на наборах. Я считаю, что он определенно квалифицируется как "элегантный", но потом я также считаю, что он квалифицируется как "своего рода немой". Вы делаете звонок.
Сначала настройте несколько таблиц:
-- 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) в каждую позицию в строке
(AB становится Cab, aCb, abC) для всех строк (Cba, bCa, baC), и у вас есть набор перестановок. Итерации по каждому результирующему набору с помощью
следующего персонажа, пока не закончите символы... или ресурсов. 10 элементов - 3,6 миллиона перестановок, примерно 48 Мбайт с вышеупомянутым алгоритмом, а 14 (уникальных) элементов достигли 87 миллиардов перестановок и 1,163 терабайта.
Я уверен, что в конечном итоге это может быть вклинилось в CTE, но в конце концов это будет прославленный цикл. Логика
яснее, и я не могу не думать, что план выполнения CTE станет кошмаром.
Ответ 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
сначала выложил некоторое время назад здесь
Однако было бы лучше сделать это на лучшем языке, таком как С# или С++.
Ответ 3
Просто используя 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
Правильно ли я понимаю, что вы построили декартово произведение n x n x n x n, а затем отфильтровываете ненужный материал? Альтернативой будет генерация всех чисел до n! а затем с помощью система факториалов, чтобы сопоставить их с помощью кодирования элементов.
Ответ 5
Проще, чем рекурсивный 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
Для произвольного количества элементов script это:
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
Этот метод использует двоичную маску для выбора правильных строк:
;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)
Я смог собрать все 3,6 миллиона решений за 3 минуты и 2 секунды. Надеюсь, это решение не будет пропущено, потому что оно не первое.
Ответ 7
Текущее решение с использованием рекурсивного 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
Предполагая, что ваша таблица называется Elements и имеет 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
Слишком много ржавчины на моих умениях 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)
Тот же принцип для 3 таблиц с добавленным CROSS JOIN
(SELECT Tres, Uno, Dos
FROM Table1
CROSS JOIN Table2 ON 1=1
CROSS JOIN Table3 ON 1=1)
хотя в объединении требуется 6 наборов кросс-объединений.