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

Откуда:
Сообщений: 283
Доброго дня.

Просьба помочь констуктивной критикой, нижеприведенная задача, по ощущениям, решена не оптимальным способом.

Условие: имеется таблица с 2 полями, необходимо сгруппировать значения таким образом,
что бы стоящие рядом, а так же стоящие рядом со стоящими рядом (рекурсивно), принадлежали к одной
и той же группе. Поиск необходимо производить по обоим столбцам.
PS
Решить с помощью рекурсивного cte не удалось.

Пример:
Пары значений
('А', 'Б')
('А', 'В')
('Г', 'Б')
('Г', 'А')
('Ж', 'А')
('В', 'Д')
('Ж', 'В')
('П', 'У')
('У', 'К')
('Е', 'Г')
Должны преобразоваться в:
1 А
1 Б
1 В
1 Г
1 Д
1 Е
1 Ж
2 К
2 П
2 У

Реализовал следующим образом (надеюсь, будет хоть немного понятно):

DECLARE @a TABLE (
	id_row int identity (1, 1) 
	,col1 NVARCHAR(10)
	,col2 NVARCHAR(10)
	)

insert into @a
values ('А', 'Б')
insert into @a
values ('А', 'В')
insert into @a
values ('Г', 'Б')
insert into @a
values ('Г', 'А')
insert into @a
values ('Ж', 'А')
insert into @a
values ('В', 'Д')
insert into @a
values ('Ж', 'В')
insert into @a
values ('П', 'У');
insert into @a
values ('У', 'К');
insert into @a
values ('Е', 'Г');

with cte as -- выбор соседних значений
(
	select col2 col, id_row from @a   -- Добавление значений вторых столбцов, иначе не попадут
	union
	select t2.col1, t1.id_row    -- соединяем с самим мобой по разноименным стобцам, выбираем значения одноименного
	from (select col1, min (id_row) id_row from @a group by col1) t1
	join  @a t2
	on t1.col1 = t2.col2
	union
	select t2.col1, t1.id_row  -- соединяем с самим мобой по одноименным стобцам, выбираем значения разноименного
	from (select col1, min (id_row) id_row from @a group by col1) t1
	join  @a t2
	on t1.col1 = t2.col1 
)

select
min(c1.id_row), 
c3.col 
from cte c1
join cte c2 on c1.col = c2.col  -- соединяем по значению, в  случае, если пересечения происходит через более чем одну итерацию
join cte c3 on c2.id_row = c3.id_row -- получаем все соседние значения для найденого на предыдущем уровне соответсвия
group by c3.col
17 мар 16, 17:32    [18944668]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
Glory
Member

Откуда:
Сообщений: 104751
baza906
что бы стоящие рядом,а так же стоящие рядом со стоящими рядом

И что показывает кто на ком стоит ?
17 мар 16, 17:43    [18944734]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
baza906
Member

Откуда:
Сообщений: 283
Glory,
под "стоящими рядом" подразумевались находящиеся в соседних столбцах
17 мар 16, 17:45    [18944741]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
Glory
Member

Откуда:
Сообщений: 104751
baza906
под "стоящими рядом" подразумевались находящиеся в соседних столбцах

И что такое "стоящие рядом со стоящими рядом" при двух столбцах ?
18 мар 16, 10:34    [18946808]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6801
baza906,

условие магистр Йода писал?
18 мар 16, 10:51    [18946884]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
Wlr-l
Member

Откуда:
Сообщений: 523
Рядом стоящие - это упорядочение по столбцам? + оконные функции, то можно попробовать так:
with A as (--исходные данные
  select *
    from (values ('А', 'Б'),
                 ('А', 'В'),
                 ('Г', 'Б'),
                 ('Г', 'А'),
                 ('Ж', 'А'),
                 ('В', 'Д'),
                 ('Ж', 'В'),
                 ('П', 'У'),
                 ('У', 'К'),
                 ('Е', 'Г')
         ) as T(m,n)
)
, B as (--упорядочиваем по столбцам
  select m,n
        ,case when m<=n then m else n end as m1
        ,case when m<=n then n else m end as n1
    from A
)
select dense_rank() over (order by m1) as r
      ,m1,n1
      ,'',m,n
  from B
 order by r,n1

Результат:
r	m1	n1	 	m	n
1 А Б А Б
1 А В А В
1 А Г Г А
1 А Ж Ж А
2 Б Г Г Б
3 В Д В Д
3 В Ж Ж В
4 Г Е Е Г
5 К У У К
6 П У П У
18 мар 16, 14:38    [18948424]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
baza906
Member

Откуда:
Сообщений: 283
Glory, допустим значение "Х" находится рядом со значением "У". В таком случае, значение "Z", которое находится рядом с "Y", должно быть причислено к той же группе, что и "Х". Как и "В", находящееся рядом с "Z"
18 мар 16, 16:23    [18949379]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
baza906
Member

Откуда:
Сообщений: 283
Wlr-l,
мне нужен на выходе другой результат. Пример описан в условии. Оконными функциями реализовать его не удалось. Но в любом случае, спасибо за внимание к моей проблеме.
18 мар 16, 16:24    [18949391]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
aleks2
Guest
Блин, как туго у молодежи с алгоритмистикой.

0. Упорядочиваем пары - первый символ ставим "меньший".
1. Всего групп = столько, сколько уникальных ПЕРВЫХ символов пар не входят ни в одну пару вторым символом.
2. Выбрать такие НАЧАЛА групп элементарно.
3. Ну и продолжаем...
4. Мне дальше скучно писать.
18 мар 16, 16:37    [18949477]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
baza906
Member

Откуда:
Сообщений: 283
aleks2,
и получится результат, как у Wlr-l, если я правильно тебя понял
18 мар 16, 17:38    [18949877]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4813
baza906,

Если я правильно понял, то надо схлопнуть кластера графа. Составить список узлов в каждой части (сегменте, кластере) графа.
18 мар 16, 18:11    [18950059]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4813
baza906,

Вот решение вашей задачи

DECLARE @a TABLE (
	id_row int identity (1, 1) 
	,col1 NVARCHAR(10)
	,col2 NVARCHAR(10)
	,Cluster INT NULL 
	)

insert into @a(col1, col2)
values ('А', 'Б')
insert into @a(col1, col2)
values ('А', 'В')
insert into @a(col1, col2)
values ('Г', 'Б')
insert into @a(col1, col2)
values ('Г', 'А')
insert into @a(col1, col2)
values ('Ж', 'А')
insert into @a(col1, col2)
values ('В', 'Д')
insert into @a(col1, col2)
values ('Ж', 'В')
insert into @a(col1, col2)
values ('П', 'У');
insert into @a(col1, col2)
values ('У', 'К');
insert into @a(col1, col2)
values ('Е', 'Г');

UPDATE @a
SET Cluster = id_row

WHILE @@ROWCOUNT > 0
BEGIN 
	UPDATE a
	SET a.Cluster = a1.Cluster
	FROM @a a
	INNER JOIN @a a1 ON (a.col1 = a1.col2 OR a.col2 = a1.col1) AND a.Cluster < a1.Cluster 
END 

SELECT * FROM @a
18 мар 16, 18:19    [18950103]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
baza906
Member

Откуда:
Сообщений: 283
a_voronin,
спасибо большое! работает отлично, остается только объединить результаты по первым двум столбцам!

вот, для интереса, моя реализация

declare @a  TABLE (
	id_row int identity (1, 1) 
	,col1 NVARCHAR(10)
	,col2 NVARCHAR(10)
	,rk int 
	)

DECLARE @output  TABLE (
	col NVARCHAR(10)
	,rk int
	,rk_min int 
	)

insert into @a (col1, col2) values ('А', 'Б')
insert into @a (col1, col2) values ('А', 'В')
insert into @a (col1, col2) values ('Г', 'Б')
insert into @a (col1, col2) values ('Г', 'А')
insert into @a (col1, col2) values ('Ж', 'А')
insert into @a (col1, col2) values ('В', 'Д')
insert into @a (col1, col2) values ('Ж', 'В')
insert into @a (col1, col2) values ('П', 'У');
insert into @a (col1, col2) values ('У', 'К');
insert into @a (col1, col2) values ('Е', 'Г');
insert into @a (col1, col2) values ('Б', 'Ю');
insert into @a (col1, col2) values ('Ю', 'Э');
insert into @a (col1, col2) values ('Э', '?');
insert into @a (col1, col2) values ('1', '2');
insert into @a (col1, col2) values ('2', '1');
insert into @a (col1, col2) values ('3', '2');

declare @column nvarchar(100)
declare @rk int = 1

DECLARE curs CURSOR FOR 
select * from
(
	SELECT col1 cl
	FROM @a
	union
	SELECT col2 cl
	FROM @a
) s
order by cl 

OPEN curs

FETCH NEXT FROM curs 
INTO @column

WHILE @@FETCH_STATUS = 0
BEGIN

	IF NOT EXISTS (select  * from @output where col = @column)
	BEGIN
		INSERT INTO @output
		VALUES (@column, @rk, @rk)
		SET @rk = @rk + 1
	END

	insert into 
	@output
	select 
	t2.col2, t1.rk, rk_min
	from 
	(select distinct col, rk, min(rk) over (partition by col) rk_min from @output) t1
	join @a t2
	on t1.col = t2.col1
	and t2.col1 = @column
	

	insert into 
	@output
	select 
	t2.col1, t1.rk, rk_min
	from  
	(select distinct col, rk, min(rk) over (partition by col) rk_min from @output) t1
	join @a t2
	on t1.col = t2.col2
	and t2.col2 = @column
	
	

FETCH NEXT FROM curs 
INTO @column
END
CLOSE curs
DEALLOCATE curs;


select distinct col, min(rk_min) over (partition by rk)
from @output
19 мар 16, 09:37    [18952315]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
iljy
Member

Откуда:
Сообщений: 8711
baza906,

чет погорячились вы с реализацией. Курсоры, оконные функции, слишком сложно все :)

select col1, col2, id_row + 0 gr into #ttt from @a

while @@ROWCOUNT >0
begin
	update t set gr = a.gr
	from #ttt t join #ttt a on (a.col1 in (t.col1, t.col2) or a.col2 in (t.col1, t.col2)) and a.gr > t.gr
end			

select col, dense_rank() over(order by MAX(gr)) gr
from (select col1 col, gr from #ttt union all select col2, gr from #ttt)t
group by col 
22 мар 16, 23:16    [18966542]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
Wlr-l
Member

Откуда:
Сообщений: 523
iljy,
"чет погорячились вы с реализацией. Курсоры, оконные функции, слишком сложно все :)"

Курсоры - да, а dense_rank() over - конечно, это не оконная функция.

Если в самом первом запросе ТС строки
select
min(c1.id_row), 

заменить на
select
dense_rank() over(order by min(c1.id_row)),

, то получится нужный результат без использования явного цикла while @@ROWCOUNT >0, уже предложенного a_voronin, + не нужно что-то менять в таблицах (update).
Т.е. самый первый запрос ТС более SQL-ский.
23 мар 16, 17:03    [18969395]     Ответить | Цитировать Сообщить модератору
 Re: Группировка в соответствии с нахождением в соседних столбцах  [new]
iljy
Member

Откуда:
Сообщений: 8711
Wlr-l,

если вы про мою реализацию, то в ней dense_rank можно смело убрать, она чисто для красоты выдачи и никакой фундаментальной нагрузки не несет.

Вторую часть утверждения я не понял, что откуда надо убрать. У a_voronin этот цикл тоже есть, я просто довел алгоритм до завершения.
23 мар 16, 18:48    [18969936]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить