2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Алгоритм разбиения на группы двух связанных множеств
Сообщение11.12.2014, 19:48 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Есть таблица примерно такого вида:
Код:
columnA    columnB
      A          1
      B          1
      B          2
      C          2
      C          3
      D          4
      D          5
      E          5
      E          6
Надо разбить строки таблицы на группы таким образом, чтобы никакие две группы не содержали общих элементов:
Код:
columnA    columnB   group
      A          1       1
      B          1       1
      B          2       1
      C          2       1
      C          3       1
      D          4       2
      D          5       2
      E          5       2
      E          6       2
В данном случае группа 1 содержит строки, в которых в первом столбце встречается A, B и C, а во втором - 1, 2 и 3. Группа 2 содержит D, E и 4, 5, 6 соответственно.
Сам алгоритм я более-менее представляю, как реализовать.
Но задача осложняется тем, что алгоритм надо реализовать на SQL, исходных данных будет много (десятки тысяч строк), а алгоритм использует рекурсию. А рекурсия в SQL при таких объемах часто требует слишком много времени работы (а то и просто можно всю память выбрать). Если существуют алгоритмы без рекурсии, буду благодарен за подсказку.

 Профиль  
                  
 
 Re: Алгоритм разбиения на группы двух связанных множеств
Сообщение11.12.2014, 22:20 
Заслуженный участник


04/05/09
4582
Ищите "поиск связных компонент в ширину", или "BFS (breadth-first search) of connected components".

 Профиль  
                  
 
 Re: Алгоритм разбиения на группы двух связанных множеств
Сообщение12.12.2014, 00:46 


24/05/09

2054
Ничё не понимаю. Последовательно проходим всю таблицу от начала до конца, где тут прикрутить рекурсию?

 Профиль  
                  
 
 Re: Алгоритм разбиения на группы двух связанных множеств
Сообщение12.12.2014, 01:21 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Alexu007 в сообщении #944639 писал(а):
Ничё не понимаю. Последовательно проходим всю таблицу от начала до конца, где тут прикрутить рекурсию?
Чтобы пройти последовательно, надо сначала расположить строки в правильной последовательности. В моем примере это только для наглядности сделано, в реальных данных такого нет.
Но если все так просто - напишите SQL запрос. Без CONNECT BY и Recursive WITH, желательно, но на худой конец и с ними пойдет.

-- 12.12.2014, 02:24 --

venco
Спасибо. Посмотрел по диагонали - показалось, что задача, видимо, не совсем для SQL. Завтра буду в деталях разбираться.

 Профиль  
                  
 
 Re: Алгоритм разбиения на группы двух связанных множеств
Сообщение27.07.2020, 00:58 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Если вдруг кому интересно - решение я нашел еще пару лет назад. Не шибко производительное (мягко говоря), с рекурсией, но зато на SQL. Требуется Oracle 11.2 или выше.

Код:
with t as (select 'A' a, 1 b from dual union all
           select 'B' a, 1 b from dual union all
           select 'B' a, 2 b from dual union all
           select 'C' a, 2 b from dual union all
           select 'C' a, 3 b from dual union all
           select 'D' a, 4 b from dual union all
           select 'D' a, 5 b from dual union all
           select 'E' a, 5 b from dual union all
           select 'E' a, 6 b from dual),
     s (a, b, root_a) as (
        select a, b, connect_by_root a root_a
                from t
             connect by nocycle (prior a =  a and prior b <> b)
                             or (prior a <> a and prior b =  b))
  select root_a, listagg(a, ',') within group (order by a) a_list
          from (select distinct root_a, a
                  from s)
         group by root_a;
Результат:
Код:
ColumnA   Group
A         A,B,C
B         A,B,C
C         A,B,C
D         D,E
E         D,E

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group