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

Есть некоторые числа заголовков (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 уже есть. Можно ставить "Вопрос решен", но если у кого-то есть еще решения, буду рад ознакомиться.

AVA12, как я понял, Majestio как раз это и сделал. Ну или очень похожее. Но задачу можно решить быстрее. Наверное. Без многократных циклов, без флагов и без возвратов. У меня один цикл... ну как один, два, но каждый со своим фильтром, непересекающимся со вторым и в точности его дополняющий. Сначала цикл пробегает по свойствам под 2-мя и более заголовками, потом ровно под одним заголовком. Так что всё равно каждое свойство получается обработанным однократно. Фактически тут O(N), где N общее количество свойств.
Меня волнует его корректность. Betelgeuse, я б поостерёгся мой алгоритм брать без досконального тестирования.

Если я правильно понял задачу, то к ней можно применить алгоритм Union-Find

Цитата Qraizer @ 25.09.23, 04:29

Но задачу можно решить быстрее. Наверное. Без многократных циклов

Хе-хе ... Ну положим, ты тут тоже малёха лукавишь В твоем варианте есть просто спрятанные "под капот" циклы, например в std::distance и keys.find

Цитата MBo @ 25.09.23, 08:30

Если я правильно понял задачу, то к ней можно применить алгоритм Union-Find

Вполне себе. Если абстрагироваться от самих "свойств", то на первом шаге вполне можно получить "матрицу отношений", а-ля:
0 0 1 0 0
0 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0

И вот из нее нужно получить вектор: (0, 1, 2), (3, 4) - это дезинфицированная Доместосом постановка задачи

MBo, пасип за идею!

Тут я уже не стал напрягаться, зарядил эту "подзадачу" реализовать ChatGPT, получилось прикольно:

#include <iostream>
#include <vector>
 
class UnionFind {
public:
  UnionFind(int n) {
    parent.resize(n);
    rank.resize(n, 0);
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
  }
 
  int find(int x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }
 
  void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
      if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
      } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
      } else {
        parent[rootY] = rootX;
        rank[rootX]++;
      }
    }
  }
 
private:
  std::vector<int> parent;
  std::vector<int> rank;
};
 
std::vector<std::vector<int>> groupElements(const std::vector<std::vector<int>>& S) {
  int n = S.size();
  UnionFind uf(n);
 
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (S[i][j] == 1) {
        uf.unite(i, j);
      }
    }
  }
 
  std::vector<std::vector<int>> groups(n);
  for (int i = 0; i < n; i++) {
    int root = uf.find(i);
    groups[root].push_back(i);
  }
 
  groups.erase(std::remove_if(groups.begin(), groups.end(), [](const std::vector<int>& group) {
    return group.empty();
  }), groups.end());
 
  return groups;
}
 
int main() {
  std::vector<std::vector<int>> S = {
    {0, 0, 1, 0, 0},
    {0, 0, 1, 0, 0},
    {1, 1, 0, 0, 0},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 1, 0}
  };
 
  std::vector<std::vector<int>> groups = groupElements(S);
 
  for (const auto& group : groups) {
    for (int element : group) {
      std::cout << element << " ";
    }
    std::cout << std::endl;
  }
 
  return 0;
}

Добавлено 25.09.23, 09:44

Цитата Qraizer @ 25.09.23, 04:29

я б поостерёгся мой алгоритм брать без досконального тестирования

И это правильно!

Вот на таких входных данных:

std::map<int, std::set<int>> source = {
                                        {1, { 1,  3,  4}}, {2, { }}, {3, {1, 4, 5}},
                                        {4, {11, 12, 14}}, {5, {10, 18, 12}}
                                      };

твой алгоритм выдает результат:

{ A : { 1 3 }:{ 1 3 4 5 } }
{ B : { 4 5 }:{ 10 11 12 14 18 } }

А у меня на аналогичных:

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

Хз, может такой тест запрещён

Цитата Majestio @ 25.09.23, 09:22

Хз, может такой тест запрещён

Если подходить к вопросу с позиции формализма теории множеств, то пустое множество входит подмножеством в любое множество, а значит его элементы принадлежат любому множеству. Из этого следует, что деление на группы будет тривиальным: просто всегда запихиваем всё в одну группу. Не думаю, что это решение. Если с позиции теории графов, что не очень похоже на исходное ТЗ, но фикъегознает, то я беспонятия.
Вообще, вопрос о выборе формализма нужно задавать Betelgeuse.

Добавлено 25.09.23, 14:14

Цитата Majestio @ 25.09.23, 09:10

Ну положим, ты тут тоже малёха лукавишь В твоем варианте есть просто спрятанные "под капот" циклы, например в std::distance и keys.find

Логично. Тогда O(N*log(N))

Цитата Qraizer @ 25.09.23, 14:12

Вообще, вопрос о выборе формализма нужно задавать Betelgeuse.

Вот тут вроде вопросов нет, читаем:

Цитата Betelgeuse @ 22.09.23, 12:35

Условие : если есть повторяющиеся свойства, они должны быть в одной группе.

Т.t. если есть элемент с пустым набором свойств, он "не повторится" ни с одним другим, даже с таким же как он.

У пустого заголовка нет свойств. ⊥ → ⊤ ≡ ⊤. Это фундаментальное свойство импликации, благодаря ему из исчисления высказываний следует, например, методика доказательств от противного.

Добавлено 25.09.23, 20:40
Чтобы такого казуса не случилось, следует кванторы всегда ограничивать по ∅. Ну или как можно чаще. Впрочем, неограниченные кванторы вообще не любят из-за конфликтов вокруг аксимы выбора.

Цитата Qraizer @ 25.09.23, 20:39

У пустого заголовка нет свойств. ⊥ → ⊤ ≡ ⊤. Это фундаментальное свойство импликации, благодаря ему из исчисления высказываний следует, например, методика доказательств от противного.
Добавлено Вчера, 23:40
Чтобы такого казуса не случилось, следует кванторы всегда ограничивать по ∅. Ну или как можно чаще. Впрочем, неограниченные кванторы вообще не любят из-за конфликтов вокруг аксимы выбора.

Не, нафик тут высшую арифметику В чисто прикладном смысле работаем. И постановщик задачи просто должен ответить на вопросы:

1) Могут ли быть элементы без характеристик (ну пустое множество это)
2) И если "да", куда их "собирать" или вообще игнорить (твой вариант)

А вообще это тема важная. Нет, не именно это пустое множество. А оптимальное начало тестов реализаций, алгоритмов. Да всего, что нужно тестировать - начинаем с "граничных" значений: нуль, ничего, пусто, очень много, очень очень много. Сразу вылезают вопросы. Ну а потом уже "обычные" тесты. Это как "обычный порошок" и "Тайд".

Скрытый текст

Примерно 1996 год. Мой неспешный переход из "теоретического программинга" (до этого работал в НИИ Технической кибернетики АН БССР, с одной персоналкой на всю лабу) - в практический (пришел в чисто девелоперскую компанию, с персональной персоналкой). Тогда еще прогал на Пасквиле. Ситуация. Парень, это тот, который когда-то меня убивал своим кодом. На Пасквиле уже не помню, напишу на Сях:

switch (idx) {
  case 65: Res = 'A'; break;
  case 66: Res = 'B'; break;
  case 67: Res = 'C'; break;
  ...
  // и так до Z, сука!!!
}

... Говорит (не дословно) "я джва года две недели вылизывал свой модуль, написал качественную документацию. Кто сможет на тестах завалить - выставляю ящик пиваса. На тест полчаса, иначе жду ящик пиваса от тестировщика. Ну я, была-не-была, подрядился. Запустил его прогу, она требует логин и пароль. Я спросил где документация. Он показал. Я открыл, не читая скопировал все в буфер обмена, переключился на диалог "логин-пароль", вставил вместо логина и пароля содержимое буфера обмена (ну собственно, его документацию), после нажатия кнопки [Login] прога легла.... А он, бедолага, тестил свои алгоритмы... Посоны были рады внезапному пивасу, и ... ржачке

Сообщение отредактировано: Qraizer - 26.09.23, 12:56

Цитата

Вообще, вопрос о выборе формализма нужно задавать Betelgeuse

у меня задача вполне прикладная. заголовков не более 10, свойств в каждом заголовке ровно по 3.
Так что пустые множества рассматривать не нужно ))

Цитата

И постановщик задачи просто должен ответить на вопросы:

1) нет
2) значит неправильные входные данные, эта ситуация будет обработана до вызова функции группировки с выводом сообщения

Сообщение отредактировано: Betelgeuse - 26.09.23, 12:15

Не даёт покоя мне это задача. Всё ж решил к ней вернуться, и не зря. И ведь было стойкое ощущение... профильник бы сразу ткнул носом. В общем, поняв, что функциями решение не выразить из-за многозначности сюръективных отношений свойств к заголовкам, начал строить решение на суръекциях, отсюда ж и всплыли мультимножества-то. Попробовав избавиться от избыточных групп, я писал реализацию постепенно шаг за шагом и удивился, получив в качестве, как мне казалось, промежуточного результата уже готовый ожидаемый. И остановился, совершенно забыв что любые многозначные отношения в природе своей индуктивны. Но у меня-то в коде нет индукции! Там только первый шаг, и мне просто "повезло" в том, что исходные данные не требовали большего их количества. Почему я этого не понял сразу , спросите лучше моё отношение к арифметике несчётных ординалов , на это я хоть что-то смогу ответить.
Занявшись серьёзным тестированием, тут же получил баг: достаточно довести отношения свойств с заголовками до второй глубины вложенности и бац! Минимальный фэйл-сценарий:
{1} : {10, 11}
{2} : {12, 13}
{3} : {11, 12} <- объединение {1} и {2} в Группу 1
{4} : {20, 21}
{5} : {22, 23}
{6} : {20, 22} <- объединение {3} и {4} в Группу 2
{7} : {12, 20} <- объединение Группы 1 с Группой 2
(Вроде, правильно воссоздал, запамятовал уже. Не всегда такая косвенность проходит незамеченной.)
Последний заголовок {7} не соотносится с {1}, {2}, {4} и {5} явно, но явно соотносится с {3} и {6}. Эта косвенная связь не будет замечена моим кодом, т.к. требует минимум двух индукционных шагов. В общем, исходно нефик было пытаться избавлять от избыточных групп. Это можно было бы сделать, только если б изначально знать глубину рекурсии, и начинать следовало бы именно с такого количества совпадений, а не ровно двух.
В общем и целом, от дополнительного уровня косвенности никуда не деться. Держите:

#include <map>
#include <set>
#include <iostream>
#include <random>
#include <string>
#include <chrono>
 
// исходный контейнер
// индексируется заголовком, содержит множества свойств для каждого
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<int, 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;
}
 
void createSource()
{
  std::mt19937                    gen;
  std::uniform_int_distribution<> numHeads(1, 10000);
  std::uniform_int_distribution<> numbers (0, 250000000);
 
  // смените на false для по-настоящему случайных входных данных
  if constexpr (true)
    gen.seed(0);
  else
    gen.seed(std::random_device()());
 
  source.clear();
  for (int i = 0; i < 1000; ++i)
  {
    decltype(source)::mapped_type set;
    int                           n = numHeads(gen);
 
    for (int j = 0; j < n; ++j)
      set.insert(numbers(gen));
    source.insert({ i, set });
  }
}
 
namespace chrono = std::chrono;
 
int main()
{
  auto            start = std::chrono::steady_clock::now();
  decltype(start) stop;
 
  createSource();
  stop = std::chrono::steady_clock::now();
  printSource();
  std::cout << "Creating src: "
            << chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1000.f
            << std::endl;
 
  std::multimap<int, int>           temp;       // контейнер обратных связей свойств => заголовки
  std::map     <int, int>           keys;       // заголовки к ключам групп
  std::map     <int, std::set<int>> names;      // группы к заголовкам
 
  start = std::chrono::steady_clock::now();
  // обращаем (заголовки => свойства) в (свойства => заголовки)
  // возможны связи многих к одному
  for (const auto& i : source)
    for (const auto& j : i.second)
      temp.insert({j, i.first});
 
  int groupName= 1;                     // будущий номер группы
  int group    = 0;                     // первый ключ группы
 
  // подбор ключей на основе поиска по связям
  for (auto it = temp.begin(); it != temp.end(); )      // для всех диапазонов свойств
  {
    auto res = temp.equal_range(it->first);             // диапазон заголовков для текущего свойства
    int  val = -1;                                      // признак не найденного ключа
 
    // по всему диапазону заголовков для текущего свойства
    for (auto bound = res.first; bound != res.second; ++bound)
    {
      auto key = keys.find(bound->second);              // ищем ключ для него
 
      if (key == keys.end()) continue;                  // если ещё не заводили, к следующему
      if (val == -1)                                    // если уже завели,
        val = key->second;                              // то ключ найден
      else                                              // иначе он был найден ранее
      {
        if (val != key->second)                         // и если он не уникален,
        {                                               // то ключи других заголовков этой группы
          auto oldKey = std::move(names[key->second]);  // нуждаются в коррекции
 
          // oldKey всегда будет найден, т.к. names модифицируется val вместе с keys
          for (auto group : oldKey)                     // скорректировать ключи всех заголовов
            keys[group] = val;                          // этой (старой) группы
          names[val].merge(oldKey);                     // старые ключи удалять нельзя, т.к. на них
        }                                               // всё ещё возможно что-то временно
      }                                                 // ссылается, т.ч. пустые группы возможны
    }
    if (val == -1)              // если ключ не был найден
      val = group++;            // завести новый
    // распространить (возможно, новый вместо старого) ключ по всему диапазону заголовков
    for (auto bound = res.first; bound != res.second; ++bound)
    {
      keys[bound->second] = val;                        // keys и names модифицируются
      names[val].insert(bound->second);                 // совместно на основе того же val
    }
    it = res.second;            // прыгнуть сразу к следующему диапазону свойств
  }
  stop = std::chrono::steady_clock::now();
  std::cout << "Grouping: "
            << chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1000.f
            << std::endl;
 
  start = std::chrono::steady_clock::now();
  // строим контейнер групп
  for (const auto& i : names)
  {
    if (i.second.empty()) continue;                             // игнорирумем пустые группы
 
    auto &it = groups[groupName++];                             // очередная непустая группа
 
    it.first.insert(i.second.begin(), i.second.end());          // множество заголовков для неё
    for (auto set : i.second)                                   // множество свойств для этих заголовков
      it.second.insert(source[set].begin(), source[set].end());
  }
  stop = std::chrono::steady_clock::now();
  std::cout << "Creating dest: "
            << chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1000.f
            << std::endl;
 
  printGroups();
}

Это полный текст, вместе с тестом. Тестится 1000 заголовков с количеством свойств от 1 до 10000. Значения свойств от 0 до 250000000. Всё случайно. В коде база рандома всегда одинакова с целью детерминированности сравнительных результатов, но её легко отключить. (Там в конце ещё был код, чекающий пересечения всех групп попарно и выводящий их, если таковые найдутся, но нынче они все пустые, как и должно быть, так что я его удалил.) Должно (Win10Pro, VS2022) получиться 6 групп.
Основные разницы от исходной реализации:

• Теперь нет нужды сортировать свойства по количеству вхождений в заголовки. Изначально было непродуктивное решение, т.к. не заменяло рекурсию. Возможно немного оптимизировало процесс, но не более. В общем, лямбды больше нет за ненадобностью.
• Появился новый контейнер names, который хранит сюръективные отношения групп к заголовкам. Его назначение в быстром поиске заголовков, чьи свойства нужно перенести из одной группы в другую.
• Названия групп решил переделать из букв в числа, т.к. диапазона char банально не хватает на таких объёмах данных. Соответственно поменялись и типы данных в связях.
• Теперь при нахождении ключа для очередного заголовка, поиск по свойству не прекращается break, и в случае, если будет найден ещё один заголовок с этом же свойством, и при этом ссылающийся на другую группу, то это признак того, что эти группы нужно объединить, что и выполняется. Это основное изменение, реализующее индукцию.

Я по-прежнему не исключаю багов в реализации, но теперь я по крайней мере спокоен по поводу корректности алгоритма. Как минимум мой вывод совпадает с выводом кода Majestio (с точностью до порядка нумерации групп, т.к. я удаляю старые группы, а его код не заводит новых), так что если у него всё верно, то и у меня тоже должно.

Добавлено 20.10.23, 16:55
P.S. Ну и особняком решил поднять вопрос производительности.

Creating src: 2.025
Grouping: 8.377
Creating dest: 5.786
 
...
 
Given time = 780.224

Это секунды. Верхние три строчки мои. Нижняя – это лобовое решение Majestio, похожее в терминах графов было предложено AVA12, но тут я не уверен. Да, сложность у меня подросла и теперь что-то вроде O(N*log(N)*log(KM)), где N общее количество свойств во всех множествах за вычетом дубликатов, M количество заголовков, а К количество дубликатов свойств. (Это если я правильно оценил.) Но даже так супротив него полуквадратичная сложность не конкурент однозначно.

P.P.S. Ещё я тестил 10000 заголовков из 1000 свойств или меньше. Получилось 516 групп. И время:

Creating src: 1.157
Grouping: 12.877
Creating dest: 6.462
 
...
 
Given time = 986922.066

Да-да, я набрался терпения и ждал 11 дней. Нужно ж было убедиться в совпадении результатов двух алгоритмов. Интересно, много ли задач из графов можно переделать в множества и применить методики оптимизации на вполне упорядоченных множествах?..

Сообщение отредактировано: Qraizer - 20.10.23, 16:59

Цитата Qraizer @ 20.10.23, 16:31

Интересно, много ли задач из графов можно переделать в множества

Очень многие. Те, что не получается переделать, обычно в терминах теории множеств не получается даже описать. Но, как правило, такая переделка мало что даёт.

Хм... Чтобы что-то нельзя было бы представить в формализме ТМ... такого не бывает.

Цитата amk @ 27.10.23, 13:02

Те, что не получается переделать, обычно в терминах теории множеств не получается даже описать.

Не понятно, но очень интересно! А можно пример по этому утверждению?