Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Снова CTE и комбинаторика  [new]
Leo Лапыч
Member

Откуда: от верблюда
Сообщений: 17
Здравствуйте!

Есть таблица с единственным столбцом
value
-----
a
b
c

Нужно получить набор данных со всеми возможными комбинациями и номером набора, то есть:
index    value
----- -----
1 a
1 b
1 c

2 a
2 c
2 b

3 b
3 a
3 c

4 b
4 c
4 a

5 c
5 a
5 b

6 c
6 b
6 a

Спасибо!
27 сен 19, 12:06    [21980735]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20538
И какой в этом смысл, если все они абсолютно идентичны?
27 сен 19, 12:42    [21980776]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
StarikNavy
Member

Откуда: Москва
Сообщений: 2396
Leo Лапыч,

фулл джоин саму на себя?
27 сен 19, 12:50    [21980785]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Shakill
Member

Откуда: мск
Сообщений: 1880
Akina
И какой в этом смысл, если все они абсолютно идентичны?

тут нужны наводящие вопросы )

Leo Лапыч, а чем у вас набор записей с index = 1 отличается от набора с index = 2? кроме самого index
27 сен 19, 12:59    [21980796]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6801
Leo Лапыч,

cross join на количество вариантов в степен длинны, в вашем случае это 3^3 и убрать дубли
27 сен 19, 13:01    [21980798]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6801
Shakill
Akina
И какой в этом смысл, если все они абсолютно идентичны?

тут нужны наводящие вопросы )

Leo Лапыч, а чем у вас набор записей с index = 1 отличается от набора с index = 2? кроме самого index

Ikshall понимает, о чём говорит
27 сен 19, 13:03    [21980801]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Leo Лапыч,

CREATE TABLE #t (value char(1));

INSERT INTO #t
(
    value
)
VALUES
('a'), ('b'), ('c');

SELECT ROW_NUMBER() OVER (ORDER BY t1.value, t2.value, t3.value) AS [index], * 
FROM #t t1
    INNER JOIN #t t2 ON t1.value != t2.value
    INNER JOIN #t t3 ON t1.value != t3.value AND t2.value != t3.value

DROP TABLE #t
27 сен 19, 13:08    [21980807]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Leo Лапыч
Member

Откуда: от верблюда
Сообщений: 17
Спасибо за ответы!

Akina
И какой в этом смысл, если все они абсолютно идентичны?
Shakill
тут нужны наводящие вопросы )
Leo Лапыч, а чем у вас набор записей с index = 1 отличается от набора с index = 2? кроме самого index
TaPaK
Ikshall понимает, о чём говорит

Суть именно в порядке их следования в результирующей выборке. Можно добавить ещё один столбец для наглядности:
set_index    value_index    value
--------- ----------- -----
1 1 a
1 2 b
1 3 c

2 1 a
2 2 c
2 3 b

3 1 b
3 2 a
3 3 c

4 1 b
4 2 c
4 3 a

5 1 c
5 2 a
5 3 b

6 1 c
6 2 b
6 3 a

Ну и для решения задачи считать, что результирующий набор данных выведен в
order by set_index, value_index
.

StarikNavy
Leo Лапыч,
фулл джоин саму на себя?

Ну если Вы получите таким образом результирующий набор данных, то прошу пример... Я лично не смог вообразить себе соединение, которое бы его дало.

TaPaK
cross join на количество вариантов в степен длинны, в вашем случае это 3^3 и убрать дубли
Minamoto
CREATE TABLE #t (value char(1));

INSERT INTO #t
(
    value
)
VALUES
('a'), ('b'), ('c');

SELECT ROW_NUMBER() OVER (ORDER BY t1.value, t2.value, t3.value) AS [index], * 
FROM #t t1
    INNER JOIN #t t2 ON t1.value != t2.value
    INNER JOIN #t t3 ON t1.value != t3.value AND t2.value != t3.value

DROP TABLE #t

Задачу нужно решить в общем виде, так как количество строк исходного набора данных может варьироваться от 1 до... скажем, 7. Распределение показательное, т.е. 1 выстреливает очень часто, а 7 - крайне редко.
27 сен 19, 13:32    [21980836]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Leo Лапыч
Задачу нужно решить в общем виде, так как количество строк исходного набора данных может варьироваться от 1 до... скажем, 7. Распределение показательное, т.е. 1 выстреливает очень часто, а 7 - крайне редко.

Пока умного общего вида не придумал, могу пока предложить тупой:

CREATE TABLE #t (value char(1));

INSERT INTO #t
(
    value
)
VALUES
('a'), ('b'), ('c'), ('d'), ('e'), ('f'), ('g');

SELECT ROW_NUMBER() OVER (ORDER BY t1.value, t2.value, t3.value, t4.value, t5.value, t6.value, t7.value) AS [index], * 
FROM #t t1
LEFT JOIN #t t2 ON t1.value != t2.value
LEFT JOIN #t t3 ON t1.value != t3.value AND t2.value != t3.value
LEFT JOIN #t t4 ON t1.value != t4.value AND t2.value != t4.value AND t3.value != t4.value
LEFT JOIN #t t5 ON t1.value != t5.value AND t2.value != t5.value AND t3.value != t5.value AND t4.value != t5.value
LEFT JOIN #t t6 ON t1.value != t6.value AND t2.value != t6.value AND t3.value != t6.value AND t4.value != t6.value AND t5.value != t6.value
LEFT JOIN #t t7 ON t1.value != t7.value AND t2.value != t7.value AND t3.value != t7.value AND t4.value != t7.value AND t5.value != t7.value AND t6.value != t7.value

DROP TABLE #t
27 сен 19, 13:58    [21980885]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Leo Лапыч
Member

Откуда: от верблюда
Сообщений: 17
Minamoto
Пока умного общего вида не придумал, могу пока предложить тупой:

CREATE TABLE #t (value char(1));

INSERT INTO #t
(
    value
)
VALUES
('a'), ('b'), ('c'), ('d'), ('e'), ('f'), ('g');

SELECT ROW_NUMBER() OVER (ORDER BY t1.value, t2.value, t3.value, t4.value, t5.value, t6.value, t7.value) AS [index], * 
FROM #t t1
LEFT JOIN #t t2 ON t1.value != t2.value
LEFT JOIN #t t3 ON t1.value != t3.value AND t2.value != t3.value
LEFT JOIN #t t4 ON t1.value != t4.value AND t2.value != t4.value AND t3.value != t4.value
LEFT JOIN #t t5 ON t1.value != t5.value AND t2.value != t5.value AND t3.value != t5.value AND t4.value != t5.value
LEFT JOIN #t t6 ON t1.value != t6.value AND t2.value != t6.value AND t3.value != t6.value AND t4.value != t6.value AND t5.value != t6.value
LEFT JOIN #t t7 ON t1.value != t7.value AND t2.value != t7.value AND t3.value != t7.value AND t4.value != t7.value AND t5.value != t7.value AND t6.value != t7.value

DROP TABLE #t

Спасибо за вариант в лоб. Если ещё дополните свой пример тем, как это привести к требуемой структуре выходных данных (индекс набора, индекс значения внутри набора, значение), то я с удовольствием возьму на вооружение, как временный вариант.

Но хотелось бы всё же увидеть мощь CTE в действии. Что-то мне подсказывает, что с помощью них можно построить подобную результирующую выборку, ведь по сути - это рекурсия, только не по дереву, а по графу.
27 сен 19, 14:33    [21980936]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
iap
Member

Откуда: Москва
Сообщений: 46983
Кол-во возможных комбинаций из n-элементов множества
27 сен 19, 14:38    [21980940]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Leo Лапыч
Member

Откуда: от верблюда
Сообщений: 17
iap
Кол-во возможных комбинаций из n-элементов множества

Пример использования CTE увидел, даже выполнил его и попробовал понять что он возвращает. Увидел некое подобие перебора вариантов, попробовал поменять значения констант,
WITH Numbers(N) AS (SELECT 1 UNION ALL SELECT N+1 FROM Numbers WHERE N<[b]7[/b])
SET @N=[b]7[/b];

но результаты вызвали лишь больше вопросов.

Ну и главное - не смог представить как туда подставить мой исходный набор данных и получить желаемый результат.
27 сен 19, 15:04    [21980969]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Leo Лапыч
Спасибо за вариант в лоб. Если ещё дополните свой пример тем, как это привести к требуемой структуре выходных данных (индекс набора, индекс значения внутри набора, значение), то я с удовольствием возьму на вооружение, как временный вариант.

Это уже скучная часть, но надо уж завершить )

CREATE TABLE #t (value char(1));

INSERT INTO #t
(
    value
)
VALUES
('a'), ('b'), ('c'), ('d'), ('e'), ('f'), ('g');

SELECT 
    ROW_NUMBER() OVER (ORDER BY t1.value, t2.value, t3.value, t4.value, t5.value, t6.value, t7.value) AS set_index, 
    t1.value AS [1],  
    t2.value AS [2],  
    t3.value AS [3],  
    t4.value AS [4],  
    t5.value AS [5],  
    t6.value AS [6],  
    t7.value AS [7]
INTO #t1
FROM 
    #t t1
    LEFT JOIN #t t2 ON t1.value != t2.value
    LEFT JOIN #t t3 ON t1.value != t3.value AND t2.value != t3.value
    LEFT JOIN #t t4 ON t1.value != t4.value AND t2.value != t4.value AND t3.value != t4.value
    LEFT JOIN #t t5 ON t1.value != t5.value AND t2.value != t5.value AND t3.value != t5.value AND t4.value != t5.value
    LEFT JOIN #t t6 ON t1.value != t6.value AND t2.value != t6.value AND t3.value != t6.value AND t4.value != t6.value AND t5.value != t6.value
    LEFT JOIN #t t7 ON t1.value != t7.value AND t2.value != t7.value AND t3.value != t7.value AND t4.value != t7.value AND t5.value != t7.value AND t6.value != t7.value

SELECT 
    unpvt.set_index, unpvt.value_index, unpvt.value
FROM 
    #t1
UNPIVOT
    (value FOR value_index IN ([1],[2], [3], [4], [5], [6], [7])) AS unpvt
ORDER BY 
    unpvt.set_index, unpvt.value_index

DROP TABLE #t
DROP TABLE #t1
27 сен 19, 15:09    [21980982]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Leo Лапыч
Member

Откуда: от верблюда
Сообщений: 17
Minamoto,

Спасибо! Решение есть.

Остаётся ещё надежда на помощь iap с CTE, так как чувствуя я, что его пример по ссылке перебором всё же занимается. Уверен, что на CTE решение должно выглядеть более изящно.
27 сен 19, 15:26    [21981005]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
msLex
Member

Откуда:
Сообщений: 8091
create table #t (
	ch char(1)
)


insert #t(
	ch
)
select 
	x.ch
from (
	values 
		('a')
		, ('b')
		, ('c')
		, ('d')
) x(ch)





; with cte as
(
	select 
		ch_sum = cast(ch as varchar(8000))
	from #t 
	union all
	select 
		ch_sum = cte.ch_sum + t.ch
	from cte 
	inner join #t t on charindex(t.ch, cte.ch_sum) = 0      
) 
select
	s.set_index
	, value_index  = charindex(t.ch, s.ch_sum)
	, value = t.ch
from (
	select 
		set_index = row_number() over(order by (ch_sum))
		, ch_sum
	from cte
	where 
		len(cte.ch_sum) = (select count(*) from #t)
) s 
inner join #t t on charindex(t.ch, s.ch_sum) > 0 
order by 
	set_index
	, value_index


drop table #t
27 сен 19, 15:31    [21981014]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20538
Leo Лапыч, да вроде в CTE должно быть не сильно сложно.

Сперва рекурсией добавляем по одному символу в конец, проверяя, что этого символа ещё нет (можно ещё и разделителем озаботиться, чтобы потом проще обратно разделять было). Соответственно рекурсия остановится, когда все символы попадут в поле. Затем отсекаем недоделанные (короткие) строки, оставляя только те, в которых есть все исходные символы, а заодно прилепляем номера будущих наборов. И потом функцией разматываем их вертикально - благо они разматываются в физическом порядке следования в разбираемой строке.
27 сен 19, 15:36    [21981023]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Leo Лапыч
Member

Откуда: от верблюда
Сообщений: 17
msLex
+
create table #t (
	ch char(1)
)


insert #t(
	ch
)
select 
	x.ch
from (
	values 
		('a')
		, ('b')
		, ('c')
		, ('d')
) x(ch)





; with cte as
(
	select 
		ch_sum = cast(ch as varchar(8000))
	from #t 
	union all
	select 
		ch_sum = cte.ch_sum + t.ch
	from cte 
	inner join #t t on charindex(t.ch, cte.ch_sum) = 0      
) 
select
	s.set_index
	, value_index  = charindex(t.ch, s.ch_sum)
	, value = t.ch
from (
	select 
		set_index = row_number() over(order by (ch_sum))
		, ch_sum
	from cte
	where 
		len(cte.ch_sum) = (select count(*) from #t)
) s 
inner join #t t on charindex(t.ch, s.ch_sum) > 0 
order by 
	set_index
	, value_index


drop table #t

Akina
+
Leo Лапыч, да вроде в CTE должно быть не сильно сложно.

Сперва рекурсией добавляем по одному символу в конец, проверяя, что этого символа ещё нет (можно ещё и разделителем озаботиться, чтобы потом проще обратно разделять было). Соответственно рекурсия остановится, когда все символы попадут в поле. Затем отсекаем недоделанные (короткие) строки, оставляя только те, в которых есть все исходные символы, а заодно прилепляем номера будущих наборов. И потом функцией разматываем их вертикально - благо они разматываются в физическом порядке следования в разбираемой строке.

Спасибо за рабочий пример! Всё-таки через создание последовательностей и функционал поиска элемента в них. Я думал, что CTE сможет прямо на лету вставлять строки в результирующую выборку, как это происходит при обходе дерева. Ну, по крайней мере, решение с использованием CTE не ограничено количеством строк исходного набора данных.
27 сен 19, 15:52    [21981058]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
msLex
Member

Откуда:
Сообщений: 8091
Leo Лапыч
Я думал, что CTE сможет прямо на лету вставлять строки в результирующую выборку, как это происходит при обходе дерева.


Так и происходит, и вы получаете ваше решение в виде дерева (я немного поменял скрипт, оставив только само дерево)


create table #t (
	ch char(1)
)


insert #t(
	ch
)
select 
	x.ch
from (
	values 
		('a')
		, ('b')
		, ('c')
		, ('d')
) x(ch)





; with cte as
(
	select 
		ch 
		, l = 0  
		, ch_sum = cast(ch as varchar(8000))
	from #t 
	union all
	select 
		t.ch
		, l = cte.l +  1
		, ch_sum = cte.ch_sum + t.ch
	from cte 
	inner join #t t on charindex(t.ch, cte.ch_sum) = 0      
) 
select
	ch = replicate('>', l) + ch
from cte 
order by 
	ch_sum
drop table #t





но вам то нужно не дерево а пути до листовых элементов (группа - это и есть полный путь)
27 сен 19, 15:59    [21981071]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
iap
Member

Откуда: Москва
Сообщений: 46983
Leo Лапыч
Ну, по крайней мере, решение с использованием CTE не ограничено количеством строк исходного набора данных.
Но это редкостный тормоз, доложу я вам!
27 сен 19, 16:47    [21981133]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
iap
Leo Лапыч
Ну, по крайней мере, решение с использованием CTE не ограничено количеством строк исходного набора данных.
Но это редкостный тормоз, доложу я вам!
Учитывая, что результативное количество строк - это факториал от исходного - в целом неудивительно.
27 сен 19, 16:55    [21981145]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Leo Лапыч
Member

Откуда: от верблюда
Сообщений: 17
msLex
+
Так и происходит, и вы получаете ваше решение в виде дерева (я немного поменял скрипт, оставив только само дерево)


create table #t (
	ch char(1)
)


insert #t(
	ch
)
select 
	x.ch
from (
	values 
		('a')
		, ('b')
		, ('c')
		, ('d')
) x(ch)





; with cte as
(
	select 
		ch 
		, l = 0  
		, ch_sum = cast(ch as varchar(8000))
	from #t 
	union all
	select 
		t.ch
		, l = cte.l +  1
		, ch_sum = cte.ch_sum + t.ch
	from cte 
	inner join #t t on charindex(t.ch, cte.ch_sum) = 0      
) 
select
	ch = replicate('>', l) + ch
from cte 
order by 
	ch_sum
drop table #t





но вам то нужно не дерево а пути до листовых элементов (группа - это и есть полный путь)
Да я уже забыл всю эту дискретную математику с её телами, полями и группами, если Вы про них.

Minamoto
Учитывая, что результативное количество строк - это факториал от исходного - в целом неудивительно.
iap
Но это редкостный тормоз, доложу я вам!
У меня при 7! выполняется одинаково быстро - меньше секунды, что меня вполне устраивает, так как 7 - это крайне редкий случай.
27 сен 19, 17:32    [21981169]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
vikkiv
Member

Откуда: London
Сообщений: 2704
если надоест лазить по кактусам то можно воспользоваться встроенными SQL Server средствами предназначенными для таких задач (хотя не у всех они настроены)например так:
declare @qry nvarchar(max)=
N'select a from(values(''a''),(''b''),(''c''),(''d''),(''e''))x(a)'
--N'select top 3[CurrencyAlternateKey]from[dbo].[DimCurrency]'
--select a from(values('a'),('b'),('c'),('d'),('c'))x(a)
--select top 3[CurrencyAlternateKey]from[dbo].[DimCurrency]
exec sp_execute_external_script @language=N'R',
@script=N'sql_ru<-function(v){n<-length(v)
if(n==1){v}else{X<-NULL
for(i in 1:n) X<-rbind(X,cbind(v[i],sql_ru(v[-i])));X}}
ou<-sql_ru(t(InputDataSet));u<-length(InputDataSet[,1])
m<-matrix(nrow=dim(ou)[1]*dim(ou)[2],ncol=3)
for(i in 1:dim(ou)[1]){for(j in 1:dim(ou)[2]){
m[u*i+j-u,3]<-ou[i,j];m[u*i+j-u,1]<-i
m[u*i+j-u,2]<-j}};OutputDataSet<-data.frame(m)',
@input_data_1=@qry
with result sets(("set"int,"seq"int,"val"varchar(6)))
27 сен 19, 19:33    [21981281]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
Leo Лапыч
Member

Откуда: от верблюда
Сообщений: 17
vikkiv
если надоест лазить по кактусам то можно воспользоваться встроенными SQL Server средствами предназначенными для таких задач (хотя не у всех они настроены)например так:
declare @qry nvarchar(max)=
N'select a from(values(''a''),(''b''),(''c''),(''d''),(''e''))x(a)'
--N'select top 3[CurrencyAlternateKey]from[dbo].[DimCurrency]'
--select a from(values('a'),('b'),('c'),('d'),('c'))x(a)
--select top 3[CurrencyAlternateKey]from[dbo].[DimCurrency]
exec sp_execute_external_script @language=N'R',
@script=N'sql_ru<-function(v){n<-length(v)
if(n==1){v}else{X<-NULL
for(i in 1:n) X<-rbind(X,cbind(v[i],sql_ru(v[-i])));X}}
ou<-sql_ru(t(InputDataSet));u<-length(InputDataSet[,1])
m<-matrix(nrow=dim(ou)[1]*dim(ou)[2],ncol=3)
for(i in 1:dim(ou)[1]){for(j in 1:dim(ou)[2]){
m[u*i+j-u,3]<-ou[i,j];m[u*i+j-u,1]<-i
m[u*i+j-u,2]<-j}};OutputDataSet<-data.frame(m)',
@input_data_1=@qry
with result sets(("set"int,"seq"int,"val"varchar(6)))
Спасибо, конечно. Но лучше уколоться об кактус, чем голой попой сесть на ежа. Так-то можно было на .NET сделать сборку и зарегистрировать её как хранимую процедуру. А интерес был именно в том, как эта задача решается на Transact-SQL с использованием обобщённых табличных выражений (или без них).
28 сен 19, 18:17    [21981717]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
PsyMisha
Member

Откуда: другая столица
Сообщений: 769
vikkiv,

Хосспади, и это такие реализации решений в этом богоподобном R, так это выглядит?
Какой ужас, честно... даже регулярные выражения в PowerShell выглядят теперь совершенно по-детски безобидно рядом с этим
30 сен 19, 09:11    [21982342]     Ответить | Цитировать Сообщить модератору
 Re: Снова CTE и комбинаторика  [new]
PsyMisha
Member

Откуда: другая столица
Сообщений: 769
vikkiv,

Хосспади, и это такие реализации решений в этом богоподобном R, так это выглядит?
Какой ужас, честно... даже регулярные выражения в PowerShell выглядят теперь совершенно по-детски безобидно рядом с этим
30 сен 19, 09:11    [21982343]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить