
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.97.9.174] |
![]() |
|
Сообщ.
#1
,
|
|
|
Есть некоторые числа заголовков (1,2,3,4,5 ...обозначены цветом) к каждому из которых есть свойства еще три числа 1=> (1,3,4) и т.д.
Прикреплённая картинка
Как сгруппировать их в Группа A, Группа B и т.д. Условие : если есть повторяющиеся свойства, они должны быть в одной группе. Заголовки идут по порядку, не повторяются, свойства могут быть любыми целыми числами. Свою попытку удалил чтобы не путала, дальше приведу код получше |
![]() |
Сообщ.
#2
,
|
|
Что-то я не осилил критерия группировки. Можно более формальное определение?
|
Сообщ.
#3
,
|
|
|
Опишу алгоритм:
Изначально нет Групп А, B (другими словами они пустые) их количество 0. Берем первого участника заголовок = 1 свойства (1,3,4), в гуппах никого нет. Создаем Гпуппу A, кладем участника заголовок = 1 со свойствами в первую группу А. Просматриваем всех оставшихся участников, у участника заголовок = 3 (1,4,5) есть совпадающая 1 из свойств Группы А, одного совпадения достаточно подходит, кладем заголовок = 3 и его свойства в группу А. Просматриваем дальше ... повторяем в случае совпадения хотя бы одного свойства. Если больше не обнаружено, но участники остались начинаем Группу Б и т.д. |
![]() |
Сообщ.
#4
,
|
|
Посмотри это:
![]() ![]() #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(); } Добавлено Если я правильно понял ТЗ, то основная проблема не в том, чтобы просканировать группы в поисках одинаковых свойств, а в том, что мы можем найти совпадение слишком поздно, когда уже (избыточно) завели новые группы. Такая ситуация, например, присутствует в заголовках 1 и 2: сканируя свойства второго заголовка, мы не найдём совпадений в свойствах первого, поэтому заведём новую группу; однако третий связывает их воедино, т.к. содержит свойства из обоих, поэтому это потребует объединения их групп с удалением избыточно заведённой. Я постарался обойтись без избыточности, т.к. удаление групп, во-первых, ведёт к дырам в их наименованиях, во-вторых, требует постоянного поиска свойств в уже обработанных заголовках на предмет этой избыточности. Сначала мы связываем "многие к одному" свойства с их заголовками, что позволит легко искать их вхождения в разные заголовки. Затем пробегаемся по построенным связям с выделением диапазонов одинаковых свойств к разным заголовкам и назначаем одну и ту же группу всем заголовкам с этой связью. Т.е. если хотя бы один заголовок из многих связанных с ним свойств уже имеет назначенную группу, распространяем связь заголовка с группой на этот заголовок. И только если ни один из заголовков ещё не связан, назначаем новую группу. При этом сначала обрабатываем те свойства, которые имеют более одной связи, что как раз и позволяет сразу устранить избыточность, т.к. диапазон одного и того же свойства включает сразу все заголовки, где они встречаются. И только потом дообрабатываем одиночные связи, которые либо попадут в одну из групп, т.к. их заголовку одна из них уже назначена, либо потребуют новой группы каждый, т.к. встречаются однократно. В заключение, чтобы построить сами группы, ещё раз оборачиваем связи заголовков к группам и опять (возможно) получаем многие к одному. Остальное дело техники. Там есть закомментированный кусок, который я использовал, чтобы чекнуть алгоритм более сложной ситуацией, с ним тоже все правильно. Вроде бы ![]() |
Сообщ.
#5
,
|
|
|
Круто !
![]() А у меня уже мысли были сделать это через рекурсию. Правда не люблю я эти рекурсии )) Пока еще подумаю над своим решением... За Ваше решение Спасибо |
![]() |
Сообщ.
#6
,
|
|
Меня не покидает ощущение, что я налажал с алгоритмом. Не могу подтвердить или опровергнуть корректность. Спецы, плз, посмотрите и покоментируйте по возможности.
|
Сообщ.
#7
,
|
|
|
Цитата Qraizer @ Меня не покидает ощущение, что я налажал с алгоритмом. Да тут с постановкой задачи и примером что-то, имхо не то! См. далее: Цитата Betelgeuse @ Опишу алгоритм: Изначально нет Групп А,B (другими словами они пустые) их количество 0 Берем первого участника заголовок = 1 свойства (1,3,4), в гуппах никого нет Создаем Гпуппу A, ложим в первую группу. Просматриваем всех оставшихся участников, у участника = 3 (1,4,5) есть совпадающая 1 из Группы А одного совпадения достаточно подходит ложим в группу А Просматриваем дальше ... повторяем в случае совпадения хотя бы одного свойства. Если больше не обнаружено, но участники остались начинаем Группу Б и т.д. * первый шаг, смотрим 1 - в группах никого нет, создаем группу А и помещаем туда 1 и его "характеристики" * второй шаг, смотрим 2 - нет ни одного повторяющегося элемента в группе А, надо по условию создавать группу Б ... а в примере элементы 2 попадают в группу А! Спрашивается WTF? ![]() * три уже не смотрим, чё делать с 2??? |
Сообщ.
#8
,
|
|
|
Цитата второй шаг, смотрим 2 - нет ни одного повторяющегося элемента в группе А, надо по условию создавать группу Б Что значит по условию нужно создавать группу Б. Вовсе нет, Группа Б должна быть создана только при условии, что в группе А собраны все совпадающие "характеристики", оставшиеся не подходят, тогда и создается группа Б Пример с сортировкой - можно ходить туда сюда сколько угодно, ведь никто не требует все отсортировать за один проход. Так и здесь. За первый проход "2" не попадает в группу А, за второй проход попадает в А, какие проблемы ? PS Возможно я сформулировал условие задачи не слишком по-программистски ... но ведь суть понятна, или нет? |
![]() |
Сообщ.
#9
,
|
|
Ну, ТЗ реально нечёткое. Но если принять во внимание пример, то получается что-то типа такого.
Рассмотрим множества свойств, определяемых заголовками. Одно множество обозначается уникальным заголовком. (Просто для удобства. ![]() Типичная задача из теории множеств, в общем-то. Особенно, если учесть, что тут все множества не просто счётны, а даже конечны. Я попытался найти решение через суръективные отображения, но в его реализации перейти к функциям не получилось из-за отношений один ко многим между заголовками и свойствами. Посему отнюдь не уверен в корректности реализации, я всё ж не математик. |
Сообщ.
#10
,
|
|
|
Цитата Betelgeuse @ 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 Некоторые замечания сразу |
![]() |
Сообщ.
#11
,
|
|
Народ, вы б хоть алгоритмы описывали. Я-то свой описал, а в ваших как разбираться-то?
|
Сообщ.
#12
,
|
|
|
Цитата Qraizer @ Народ, вы б хоть алгоритмы описывали. Я-то свой описал, а в ваших как разбираться-то? Ок, опишу свой. Алгоритм обработки я реализовал в виде автомата состояний, который крутится в цикле, ну это и по коду видно. По постановке задачи я выделил четыре состояния, которые также видны в коде (блок switch): Ну и некоторые детали: Боюсь что несколько сумбурно описал, но очень надеюсь, что поймёте ![]() |
Сообщ.
#13
,
|
|
|
Majestio Спасибо
|
Сообщ.
#14
,
|
|
|
Что-то алгоритмы у вас больно мудреные и "низкоуровневые". Можно ведь написать проще:
Имеется граф, содержащий вершины двух типов: заголовок и свойство. Каждое ребро соединяет заголовок со свойством. Нужно найти все компоненты связности (группы), для каждой группы построить список заголовков и свойств. Для каждого заголовка и свойства будем хранить метку посетили/не посетили, изначально все вершины не посещены. В цикле берем любую непомеченную вершину и начиная с нее обходим граф в ширину. Уже помеченные вершины при обходе пропускаются, каждая посещенная вершина помечается. Каждый помеченный заголовок добавляется в список заголовков группы, каждое помеченное свойство добавляем в список свойств группы. Когда обход завершен, выполняем новую итерацию цикла для новой группы, пока есть непомеченные вершины. |
Сообщ.
#15
,
|
|
|
Два отличных решения от Qraizer и Majestio уже есть. Можно ставить "Вопрос решен", но если у кого-то есть еще решения, буду рад ознакомиться.
|
![]() |
Сообщ.
#16
,
|
|
AVA12, как я понял, Majestio как раз это и сделал. Ну или очень похожее. Но задачу можно решить быстрее. Наверное. Без многократных циклов, без флагов и без возвратов. У меня один цикл... ну как один, два, но каждый со своим фильтром, непересекающимся со вторым и в точности его дополняющий. Сначала цикл пробегает по свойствам под 2-мя и более заголовками, потом ровно под одним заголовком. Так что всё равно каждое свойство получается обработанным однократно. Фактически тут O(N), где N общее количество свойств.
Меня волнует его корректность. Betelgeuse, я б поостерёгся мой алгоритм брать без досконального тестирования. |
Сообщ.
#17
,
|
|
|
Если я правильно понял задачу, то к ней можно применить алгоритм Union-Find
|
Сообщ.
#18
,
|
|
|
Цитата Qraizer @ Но задачу можно решить быстрее. Наверное. Без многократных циклов Хе-хе ... Ну положим, ты тут тоже малёха лукавишь ![]() ![]() Цитата MBo @ Если я правильно понял задачу, то к ней можно применить алгоритм 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) - это дезинфицированная Доместосом постановка задачи ![]() |
Сообщ.
#19
,
|
|
|
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; } Добавлено Цитата Qraizer @ я б поостерёгся мой алгоритм брать без досконального тестирования И это правильно! ![]() Вот на таких входных данных: ![]() ![]() 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: Хз, может такой тест запрещён ![]() |
![]() |
Сообщ.
#20
,
|
|
Цитата Majestio @ Если подходить к вопросу с позиции формализма теории множеств, то пустое множество входит подмножеством в любое множество, а значит его элементы принадлежат любому множеству. Из этого следует, что деление на группы будет тривиальным: просто всегда запихиваем всё в одну группу. Не думаю, что это решение. Если с позиции теории графов, что не очень похоже на исходное ТЗ, но фикъегознает, то я беспонятия.Хз, может такой тест запрещён Вообще, вопрос о выборе формализма нужно задавать Betelgeuse. Добавлено Цитата Majestio @ Логично. Тогда O(N*log(N)) Ну положим, ты тут тоже малёха лукавишь В твоем варианте есть просто спрятанные "под капот" циклы, например в std::distance и keys.find |
Сообщ.
#21
,
|
|
|
Цитата Qraizer @ Вообще, вопрос о выборе формализма нужно задавать Betelgeuse. Вот тут вроде вопросов нет, читаем: Цитата Betelgeuse @ Условие : если есть повторяющиеся свойства, они должны быть в одной группе. Т.t. если есть элемент с пустым набором свойств, он "не повторится" ни с одним другим, даже с таким же как он. |
![]() |
Сообщ.
#22
,
|
|
У пустого заголовка нет свойств. ⊥ → ⊤ ≡ ⊤. Это фундаментальное свойство импликации, благодаря ему из исчисления высказываний следует, например, методика доказательств от противного.
Добавлено Чтобы такого казуса не случилось, следует кванторы всегда ограничивать по ∅. Ну или как можно чаще. Впрочем, неограниченные кванторы вообще не любят из-за конфликтов вокруг аксимы выбора. |
Сообщ.
#23
,
|
|
|
Цитата Qraizer @ У пустого заголовка нет свойств. ⊥ → ⊤ ≡ ⊤. Это фундаментальное свойство импликации, благодаря ему из исчисления высказываний следует, например, методика доказательств от противного. Добавлено Вчера, 23:40 Чтобы такого казуса не случилось, следует кванторы всегда ограничивать по ∅. Ну или как можно чаще. Впрочем, неограниченные кванторы вообще не любят из-за конфликтов вокруг аксимы выбора. Не, нафик тут высшую арифметику ![]() 1) Могут ли быть элементы без характеристик (ну пустое множество это) 2) И если "да", куда их "собирать" или вообще игнорить (твой вариант) А вообще это тема важная. Нет, не именно это пустое множество. А оптимальное начало тестов реализаций, алгоритмов. Да всего, что нужно тестировать - начинаем с "граничных" значений: нуль, ничего, пусто, очень много, очень очень много. Сразу вылезают вопросы. Ну а потом уже "обычные" тесты. Это как "обычный порошок" и "Тайд". Скрытый текст Примерно 1996 год. Мой неспешный переход из "теоретического программинга" (до этого работал в НИИ Технической кибернетики АН БССР, с одной персоналкой на всю лабу) - в практический (пришел в чисто девелоперскую компанию, с персональной персоналкой). Тогда еще прогал на Пасквиле. Ситуация. Парень, это тот, который когда-то меня убивал своим кодом. На Пасквиле уже не помню, напишу на Сях: ![]() ![]() switch (idx) { case 65: Res = 'A'; break; case 66: Res = 'B'; break; case 67: Res = 'C'; break; ... // и так до Z, сука!!! } ... Говорит (не дословно) "я ![]() |
Сообщ.
#24
,
|
|
|
Цитата Вообще, вопрос о выборе формализма нужно задавать Betelgeuse у меня задача вполне прикладная. заголовков не более 10, свойств в каждом заголовке ровно по 3. Так что пустые множества рассматривать не нужно )) Цитата И постановщик задачи просто должен ответить на вопросы: 1) нет 2) значит неправильные входные данные, эта ситуация будет обработана до вызова функции группировки с выводом сообщения |
![]() |
Сообщ.
#25
,
|
|
Не даёт покоя мне это задача. Всё ж решил к ней вернуться, и не зря. И ведь было стойкое ощущение... профильник бы сразу ткнул носом. В общем, поняв, что функциями решение не выразить из-за многозначности сюръективных отношений свойств к заголовкам, начал строить решение на суръекциях, отсюда ж и всплыли мультимножества-то. Попробовав избавиться от избыточных групп, я писал реализацию постепенно шаг за шагом и удивился, получив в качестве, как мне казалось, промежуточного результата уже готовый ожидаемый. И остановился, совершенно забыв что любые многозначные отношения в природе своей индуктивны. Но у меня-то в коде нет индукции! Там только первый шаг, и мне просто "повезло" в том, что исходные данные не требовали большего их количества. Почему я этого не понял сразу
![]() ![]() Занявшись серьёзным тестированием, тут же получил баг: достаточно довести отношения свойств с заголовками до второй глубины вложенности и бац! Минимальный фэйл-сценарий: {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(); } Основные разницы от исходной реализации: Я по-прежнему не исключаю багов в реализации, но теперь я по крайней мере спокоен по поводу корректности алгоритма. Как минимум мой вывод совпадает с выводом кода Majestio (с точностью до порядка нумерации групп, т.к. я удаляю старые группы, а его код не заводит новых), так что если у него всё верно, то и у меня тоже должно. Добавлено P.S. Ну и особняком решил поднять вопрос производительности. ![]() ![]() Creating src: 2.025 Grouping: 8.377 Creating dest: 5.786 ... Given time = 780.224 P.P.S. Ещё я тестил 10000 заголовков из 1000 свойств или меньше. Получилось 516 групп. И время: ![]() ![]() Creating src: 1.157 Grouping: 12.877 Creating dest: 6.462 ... Given time = 986922.066 |
Сообщ.
#26
,
|
|
|
Цитата Qraizer @ Очень многие. Те, что не получается переделать, обычно в терминах теории множеств не получается даже описать. Но, как правило, такая переделка мало что даёт. Интересно, много ли задач из графов можно переделать в множества |
![]() |
Сообщ.
#27
,
|
|
Хм... Чтобы что-то нельзя было бы представить в формализме ТМ... такого не бывает.
|
Сообщ.
#28
,
|
|
|
Цитата amk @ Те, что не получается переделать, обычно в терминах теории множеств не получается даже описать. Не понятно, но очень интересно! ![]() |