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

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

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

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