Как сгруппировать элементы

Есть некоторые числа заголовков (1,2,3,4,5 ...обозначены цветом) к каждому из которых есть свойства еще три числа 1=> (1,3,4) и т.д.

Прикреплённая картинка

Как сгруппировать их в Группа A, Группа B и т.д.
Условие : если есть повторяющиеся свойства, они должны быть в одной группе.
Заголовки идут по порядку, не повторяются, свойства могут быть любыми целыми числами.

Свою попытку удалил чтобы не путала, дальше приведу код получше

Сообщение отредактировано: Betelgeuse - 24.09.23, 06:13

Что-то я не осилил критерия группировки. Можно более формальное определение?

Опишу алгоритм:

Изначально нет Групп А, B (другими словами они пустые) их количество 0.
Берем первого участника заголовок = 1 свойства (1,3,4), в гуппах никого нет. Создаем Гпуппу A, кладем участника заголовок = 1 со свойствами в первую группу А.
Просматриваем всех оставшихся участников, у участника заголовок = 3 (1,4,5) есть совпадающая 1 из свойств Группы А, одного совпадения достаточно подходит, кладем заголовок = 3 и его свойства в группу А.
Просматриваем дальше ... повторяем в случае совпадения хотя бы одного свойства.
Если больше не обнаружено, но участники остались начинаем Группу Б и т.д.

Сообщение отредактировано: Betelgeuse - 24.09.23, 06:16

Посмотри это:

#include <map>
#include <set>
#include <iostream>
 
// исходный контейнер
// индексируется заголовком, содержит множества свойств для каждого
std::map<int, std::set<int>> source = {
                                        {1, { 1,  3,  4}}, {2, { 5,  6,  8}}, {3, {1, 4, 5}},
                                        {4, {11, 12, 14}}, {5, {10, 18, 12}}
                                      };
/*                                      {
                                        {1, { 1,  3}}, {2, { 5,  6}}, {3, {2, 4}}, {9, {0}},
                                        {4, {11, 12, 14}}, {5, {10, 18, 12}}, {8, {6, 2}}
                                      };*/
 
// контейнер групп
// индексируется ключём группы, для каждого содержит два множества:
// заголовки как first и свойства как second в паре
std::map<char, std::pair<std::set<int>, std::set<int>>> groups;
 
void printSource()
{
  for (const auto& i : source)
  {
    std::cout << "{ " << i.first << " : { ";
    for (const auto& j : i.second)
      std::cout << j << ' ';
    std::cout << "} }\n";
  }
  std::cout << std::endl;
}
 
void printGroups()
{
  for (const auto& i : groups)
  {
    std::cout << "{ " << i.first << " : { ";
    for (const auto& j : i.second.first)
      std::cout << j << ' ';
    std::cout << "}:{ ";
    for (const auto& j : i.second.second)
      std::cout << j << ' ';
    std::cout << "} }\n";
  }
  std::cout << std::endl;
}
 
int main()
{
  printSource();
 
  std::multimap<int, int > temp;        // контейнер обратных связей свойств => заголовки
  std::map     <int, char> keys;        // уникальные ключи групп заголовков
 
  // обращаем (заголовки => свойства) в (свойства => заголовки)
  // возможны связи многих к одному
  for (const auto& i : source)
    for (const auto& j : i.second)
      temp.insert({j, i.first});
 
  char group    = 'A';                  // первый ключ группы
  auto fillKeys = [&](bool aloned)      // подбор ключей на основе поиска по связям
                     {
                       for (auto it = temp.begin(); it != temp.end(); ) // для всех диапазонов
                       {
                         auto res = temp.equal_range(it->first);// диапазон заголовков для свойства
 
                         // тут ищутся либо уникальные (aloned == true), либо неуникальные связи
                         if (std::distance(res.first, res.second) == 1 == aloned)
                         {
                           char val = '\0';     // признак не найденного
 
                           // по всему диапазону заголовков для текущего свойства
                           for (auto bound = res.first; bound != res.second; ++bound)
                           {
                             auto key = keys.find(bound->second);       // ищем ключ для него
 
                             if (key == keys.end()) continue;   // если ещё не заводили, к следующему
                             val = key->second;                 // если уже завели, то ключ найден
                             break;                             // и остальные можно не смотреть
                           }
                           if (val == '\0')             // если ключ не был найден
                             val = group++;             // завести новый
                           // расспространить ключ по всему диапазону заголовков
                           for (auto bound = res.first; bound != res.second; ++bound)
                             keys.insert({bound->second, val});
                         }
                         it = res.second;       // прыгнуть сразу к следующему диапазону свойств
                       }
                     };
 
  // строим связи заголовков к группам
  fillKeys(false);      // сначала обработать неуникальные связи (многие к одному)
  fillKeys(true);       // затем дообработать уникальные (один к одному)
  
  std::multimap<char, int> reverse;     // контейнер обратных связей ключи => заголовки
 
  // обратить связи (заголовки => ключи) в (ключи => заголовки)
  // возможны связи многих к одному
  for (const auto& i : keys)
    reverse.insert({i.second, i.first});
  // строим контейнер групп
  for (const auto& i : reverse)
  {
    auto& it = groups[i.first];                                         // очередная группа
 
    it.first.insert(i.second);                                          // множество заголовков для неё
    it.second.insert(source[i.second].begin(), source[i.second].end()); // множество свойств для этих заголовков
  }
 
  printGroups();
}

Код без гарантий. Работать должен, но нужно серьёзное тестирование.

Добавлено 22.09.23, 18:28
Если я правильно понял ТЗ, то основная проблема не в том, чтобы просканировать группы в поисках одинаковых свойств, а в том, что мы можем найти совпадение слишком поздно, когда уже (избыточно) завели новые группы. Такая ситуация, например, присутствует в заголовках 1 и 2: сканируя свойства второго заголовка, мы не найдём совпадений в свойствах первого, поэтому заведём новую группу; однако третий связывает их воедино, т.к. содержит свойства из обоих, поэтому это потребует объединения их групп с удалением избыточно заведённой.
Я постарался обойтись без избыточности, т.к. удаление групп, во-первых, ведёт к дырам в их наименованиях, во-вторых, требует постоянного поиска свойств в уже обработанных заголовках на предмет этой избыточности. Сначала мы связываем "многие к одному" свойства с их заголовками, что позволит легко искать их вхождения в разные заголовки. Затем пробегаемся по построенным связям с выделением диапазонов одинаковых свойств к разным заголовкам и назначаем одну и ту же группу всем заголовкам с этой связью. Т.е. если хотя бы один заголовок из многих связанных с ним свойств уже имеет назначенную группу, распространяем связь заголовка с группой на этот заголовок. И только если ни один из заголовков ещё не связан, назначаем новую группу. При этом сначала обрабатываем те свойства, которые имеют более одной связи, что как раз и позволяет сразу устранить избыточность, т.к. диапазон одного и того же свойства включает сразу все заголовки, где они встречаются. И только потом дообрабатываем одиночные связи, которые либо попадут в одну из групп, т.к. их заголовку одна из них уже назначена, либо потребуют новой группы каждый, т.к. встречаются однократно.
В заключение, чтобы построить сами группы, ещё раз оборачиваем связи заголовков к группам и опять (возможно) получаем многие к одному. Остальное дело техники. Там есть закомментированный кусок, который я использовал, чтобы чекнуть алгоритм более сложной ситуацией, с ним тоже все правильно. Вроде бы ...

Круто !
А у меня уже мысли были сделать это через рекурсию. Правда не люблю я эти рекурсии )) Пока еще подумаю над своим решением...
За Ваше решение Спасибо

Меня не покидает ощущение, что я налажал с алгоритмом. Не могу подтвердить или опровергнуть корректность. Спецы, плз, посмотрите и покоментируйте по возможности.

Цитата Qraizer @ 23.09.23, 15:45

Меня не покидает ощущение, что я налажал с алгоритмом.

Да тут с постановкой задачи и примером что-то, имхо не то! См. далее:

Цитата Betelgeuse @ 22.09.23, 13:23

Опишу алгоритм:
Изначально нет Групп А,B (другими словами они пустые) их количество 0

Берем первого участника заголовок = 1 свойства (1,3,4), в гуппах никого нет Создаем Гпуппу A, ложим в первую группу.

Просматриваем всех оставшихся участников, у участника = 3 (1,4,5) есть совпадающая 1 из Группы А одного совпадения достаточно подходит
ложим в группу А

Просматриваем дальше ... повторяем в случае совпадения хотя бы одного свойства.

Если больше не обнаружено, но участники остались начинаем Группу Б и т.д.

* первый шаг, смотрим 1 - в группах никого нет, создаем группу А и помещаем туда 1 и его "характеристики"
* второй шаг, смотрим 2 - нет ни одного повторяющегося элемента в группе А, надо по условию создавать группу Б ... а в примере элементы 2 попадают в группу А! Спрашивается WTF?
* три уже не смотрим, чё делать с 2???

Цитата

второй шаг, смотрим 2 - нет ни одного повторяющегося элемента в группе А, надо по условию создавать группу Б

Что значит по условию нужно создавать группу Б. Вовсе нет, Группа Б должна быть создана только при условии, что в группе А собраны все совпадающие "характеристики", оставшиеся не подходят, тогда и создается группа Б

Пример с сортировкой - можно ходить туда сюда сколько угодно, ведь никто не требует все отсортировать за один проход.
Так и здесь. За первый проход "2" не попадает в группу А, за второй проход попадает в А, какие проблемы ?

PS Возможно я сформулировал условие задачи не слишком по-программистски ... но ведь суть понятна, или нет?

Сообщение отредактировано: Betelgeuse - 27.09.23, 08:23

Ну, ТЗ реально нечёткое. Но если принять во внимание пример, то получается что-то типа такого.
Рассмотрим множества свойств, определяемых заголовками. Одно множество обозначается уникальным заголовком. (Просто для удобства. ) Группы суть тоже множества свойств, образуются объединением нескольких множеств свойств (но не групп), в частном случае группа – это одно множество. Деление на группы подчиняется правилу, что пересечением любых двух групп является пустое множество. Требуется распределить множества по группам так, чтобы минимизировать количество групп.
Типичная задача из теории множеств, в общем-то. Особенно, если учесть, что тут все множества не просто счётны, а даже конечны. Я попытался найти решение через суръективные отображения, но в его реализации перейти к функциям не получилось из-за отношений один ко многим между заголовками и свойствами. Посему отнюдь не уверен в корректности реализации, я всё ж не математик.

Сообщение отредактировано: Qraizer - 24.09.23, 00:11

Цитата Betelgeuse @ 23.09.23, 22:03

PS Возможно я сформулировал условие задачи не слишком по-программистски ... но ведь суть понятна, или нет?

Вроде понял. Держи мой вариант (а тут он онлайн):

#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <vector>
#include <set>
 
using SourceType = std::vector<std::pair<std::size_t, std::set<int>>>;
using ResultType = std::vector<std::pair<std::vector<std::size_t>, std::set<int>>>;
 
int main() {
    // исходные данные
    SourceType S = {
        { 1, { 1,  3,  4 }},
        { 2, { 5,  6,  8 }},
        { 3, { 1,  4,  5 }},
        { 4, {11, 12, 14 }},
        { 5, {10, 18, 12 }}
    };
    // получаемые данные
    ResultType R;
    // текущий индекс обработчика
    std::size_t Jump = (S.size()) ? 2 : 0;
    // текущий индекс обрабатываемого элемента
    std::size_t IdxS = 0;
    // текущий индекс элемента группы
    std::size_t IdxR = 0;
    // поехали
    while (Jump) {
        switch (Jump) {
            case 1: // проверка на необходимость дальнейшей обработки
                Jump = (S.size()) ? 4 : 0;
                break;
            case 2: // создание группы
                R.push_back({{}, {}});
                IdxR = R.size() - 1;
            case 3: // занесение в группу текущего элемента
                R[IdxR].first.push_back(S[IdxS].first);
                R[IdxR].second.merge(S[IdxS].second);
                S.erase(S.begin() + IdxS);
                IdxS = 0;
                IdxR = 0;
                Jump = 1;
                break;
            case 4: // проверка необходимости занесения текущего элемента в текущую группу
                std::set<int> intersection;
                std::set_intersection(S[IdxS].second.begin(), S[IdxS].second.end(), R[IdxR].second.begin(), R[IdxR].second.end(), std::inserter(intersection, intersection.begin()));
                if (intersection.empty()) {
                    if (IdxR + 1 < R.size())
                        IdxR++;
                    else {
                        if (IdxS + 1 < S.size()) {
                            IdxS++;
                            IdxR = 0;
                            Jump = 1;
                        } else
                            Jump = 2;
                    }
                } else
                    Jump = 3;
        }
    }
    // Печать результата
    char Curr = 'A';
    std::cout << std::endl;
    for (auto& i : R) {
        std::ostringstream ossg;
        std::sort(i.first.begin(), i.first.end());
        std::copy(i.first.begin(), i.first.end(), std::ostream_iterator<int>(ossg, " "));
        std::cout << "Group [" << Curr++ << "]: " << ossg.str() << std::endl;
        std::ostringstream ossb;
        std::copy(i.second.begin(), i.second.end(), std::ostream_iterator<int>(ossb, " "));
        std::cout << "   bitset: " << ossb.str() << std::endl;
    }
    std::cout << std::endl;
    return 0;
}

Вывод:

Group [A]: 1 2 3
   bitset: 1 3 4 5 6 8
Group [B]: 4 5
   bitset: 10 11 12 14 18

Некоторые замечания сразу

• Компилиться под C++17 и выше из-за использования merge для std::set, лениво универсалить
• Не использовал std::map, т.к. вижу идут цифровые идентификаторы подряд, если нужно - можно и карты впилить

Народ, вы б хоть алгоритмы описывали. Я-то свой описал, а в ваших как разбираться-то?

Цитата Qraizer @ 24.09.23, 07:43

Народ, вы б хоть алгоритмы описывали. Я-то свой описал, а в ваших как разбираться-то?

Ок, опишу свой. Алгоритм обработки я реализовал в виде автомата состояний, который крутится в цикле, ну это и по коду видно. По постановке задачи я выделил четыре состояния, которые также видны в коде (блок switch):

1. Состояние анализа завершения работы автомата
2. Состояние создания новой группы в переменной-результате
3. Состояние внесения текущего рассматриваемого элемента в текущую группу
4. Состояние анализа текущего элемента, что с ним делать - поместить в текущую группу или создать для него новую группу

Ну и некоторые детали:

• В начале обработки первый элемент всегда создает первую группу (вернее первый элемент в векторе групп)
• Если элемент попал в группу - он удаляется из исходных данных, соответственно больше в обработке не участвует, и индексы элемента и группы - все в нуль
• Если текущий элемент пересекается по множеству характеристик с текущим элементом групп, он помещается в текущий элемент групп, индексы все в нуль, обработка продолжается
• Если текущий элемент не пересекается по множеству характеристик с текущим элементом групп, делается "попытка" увеличения индекса группы и повторное сравнение уже со следующим элементом групп
• Если текущий элемент не пересекается по множеству характеристик с текущей элементом групп, и текущий элемент группы в списке последний - текущей индекс группы обнуляется и делается попытка выборки следующего элемента из списка
• Если текущий элемент последний и он не пресекается с последним элементом в группах - создается новый элемент в списке групп и туда помещается текущий элемент, индексы обнуляются и начинается очередной цикл анализа-сравнений
• Автомат завершает свою работу если список элементов стал пустым

Боюсь что несколько сумбурно описал, но очень надеюсь, что поймёте

Majestio Спасибо

Что-то алгоритмы у вас больно мудреные и "низкоуровневые". Можно ведь написать проще:

Имеется граф, содержащий вершины двух типов: заголовок и свойство. Каждое ребро соединяет заголовок со свойством. Нужно найти все компоненты связности (группы), для каждой группы построить список заголовков и свойств.

Для каждого заголовка и свойства будем хранить метку посетили/не посетили, изначально все вершины не посещены.
В цикле берем любую непомеченную вершину и начиная с нее обходим граф в ширину. Уже помеченные вершины при обходе пропускаются, каждая посещенная вершина помечается. Каждый помеченный заголовок добавляется в список заголовков группы, каждое помеченное свойство добавляем в список свойств группы. Когда обход завершен, выполняем новую итерацию цикла для новой группы, пока есть непомеченные вершины.

Два отличных решения от Qraizer и Majestio уже есть. Можно ставить "Вопрос решен", но если у кого-то есть еще решения, буду рад ознакомиться.