![>](style_images/1/nav_m.gif)
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.147.67.246] |
![]() |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#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 уже есть. Можно ставить "Вопрос решен", но если у кого-то есть еще решения, буду рад ознакомиться.
|