Обобщение «удалить все дубликаты»

Question

Позвольте related быть двоичным предикатом. Определим «подмножество отношений» как множество всех элементов, так что любой элемент в подмножестве связан с хотя бы одним другим элементом в подмножестве через «родственный», отличный от него (отсюда, связан ли элемент с самим собой или не имеет никакого отношения к формированию подмножеств отношения). Примечание: подмножество отношения НЕ обязательно strongly connected component. Например, предположим, что A связано с B, а B и C связаны друг с другом. Тогда {A, B, C} является подмножеством отношений по определению, но не является сильно связанным компонентом, потому что нет пути от B до A или от C до A через 'related'.

Обратите внимание, что «связанный» не обязательно является симметричным, т. Е. Связанный (a, b) == true не обязательно означает, что связанный (b, a) == true и не является транзитивным, то есть связанным (a, b) == true и связанные (b, c) == true не обязательно подразумевают взаимосвязанные (a, c) == true. Насколько я могу судить, никаких ограничений на бинарный предикат related не требуется, чтобы разбить набор на подмножества отношений. Если элемент x не связан ни с каким элементом вообще (кроме него самого), то {x} сам является его собственным подмножеством отношений.

Одна хорошая проблема заключается в определении

template <typename Container, typename BinaryPredicate> 
void partition (Container& container, BinaryPredicate related); 

, что будет сортировать элементы контейнера, так что контейнер разбивается на его отношение подмножеств. Этот вопрос быстро возникла после попытки исходную задачу:

template <typename Container, typename BinaryPredicate> 
void removeRelated (Container& container, BinaryPredicate related); 

, которая заключается в удалении (от container) все элементы из каждого подмножества отношения, для первого из каждого подмножества, найденного в контейнере, за исключением.

Конечно, равенство является лишь частным случаем «связанных», и, следовательно, это обобщение «удалить все дубликаты» (так я придумал этот вопрос, пытаясь обобщить эту хорошо известную решаемую проблему). Мы хотим сохранить один представитель каждого подмножества отношений, а именно первый в соответствии с упорядочением элементов контейнера.

Ниже приведен код, я пытался реализовать, со следующими соотношениями:

Bob knows Mary 
Mary knows Jim 
Jim knows Bob 
Sally knows Fred 
Fred knows no one. 

В этом примере А связана с B тогда и только тогда, когда знает Б. {Боб, Мэри, Джим} является подмножество отношений, потому что каждый человек связан с кем-то другим (Боб связан с Мэри, Мэри связана с Джим, Джим связан с Бобом). Обратите внимание, что {Sally, Fred} НЕ является подмножеством отношений, потому что, хотя Салли связана с Фредом, Фред не связан с Салли. Таким образом, мы остаемся с {Sally}, {Fred} как другие два подмножества отношений.

Итак, окончательный ответ должен быть: Боб, Салли, Фред. Обратите внимание: если бы функция partition была определена, она просто оставила бы (Боб, Мэри, Джим, Салли, Фред) без изменений, а Боб, Салли, Фред стал первым элементом каждого раздела. Следовательно, даже если бы у нас была функция partition (не путать с std :: partition, конечно, но я сейчас не думаю о хорошем имени), все равно не сразу понятно, что нужно removeRelated.

#include <iostream> 
#include <algorithm> 
#include <list> 
#include <set> 

template<typename Container, typename BinaryPredicate> 
void removeRelated (Container& container, BinaryPredicate related) { 
    using element = typename Container::value_type; 
    std::set<element> s; 
    for (typename Container::iterator it = std::begin(container); it != std::end(container);) { 
     if (std::find_if(s.begin(), s.end(), 
       [=](const element& x)->bool {return related(*it,x);}) != s.end()) 
      it = container.erase(it); // *it is related to an element in s. 
     else { 
      s.insert(*it); 
      it++; 
     } 
    } 
} 

struct Person { // Used for testing removeRelated. 
    std::string name; 
    std::list<Person*> peopleKnown; 
    Person (const std::string& n) : name(n) {} 
    void learnsAbout (Person* p) {peopleKnown.push_back(p);} 
    bool knows (Person* p) const { 
     return std::find(peopleKnown.begin(), peopleKnown.end(), p) != peopleKnown.end(); 
    } 
}; 

int main() { 
    Person *bob = new Person("Bob"), *mary = new Person("Mary"), *jim = new Person("Jim"), 
     *sally = new Person("Sally"), *fred = new Person("Fred"); 
    bob->learnsAbout(mary); 
    mary->learnsAbout(jim); 
    jim->learnsAbout(bob); 
    sally->learnsAbout(fred); 
    std::list<Person*> everybody {bob, mary, jim, sally, fred}; 
    removeRelated (everybody, [](Person* a, Person* b)->bool {return a->knows(b);}); 
    for (const Person* x : everybody) std::cout << x->name << ' '; // Bob Mary Sally Fred 
// Should be 'Bob Sally Fred' since {Bob, Mary, Jim}, {Sally}, {Fred} are the relation subsets. 
} 

Исправлена ​​ошибка, из приведенного выше кода является то, что Мария вставляется в «с», потому что в тот момент она не имеет отношения к любому в сек (через «знает»). В конце концов, она связана с Джимом, который связан с Бобом (и Бобом с Марией) через «знает», и, следовательно, {Bob, Mary, Jim} является подмножеством отношений, поэтому bob должен быть единственным из этих трех люди в России ».

Но во время итерации функция этого не знает. Как я могу исправить алгоритм? Одна из идей состоит в том, чтобы, возможно, сначала определить указанную выше функцию partition, то есть сортировать контейнер, чтобы контейнер был разделен на его подмножества отношения (что само по себе является очень приятной проблемой и вполне может быть основным вопросом) , а затем просто возьмите первый элемент каждого раздела.

Другая идея заключается в замене лямбда-функции

[=](const element& x)->bool {return related(*it,x);} 

с

[=](const element& x)->bool {return relatedIndirectly(*it,x);} 

, и я думаю, что это может решить проблему, где вспомогательная функция relatedIndirectly ищет цепочку отношений к х.

Вот еще один пример, рассмотренный Cimbali (см. Ниже). Предположим, что A связано с B, A связано с C, B связано с C. Тогда {A, B} не может быть подмножеством отношений, потому что B не связано с A. Аналогично, {A, C} и {B, C} не может быть подмножествами отношений (C не связан с A, а C не связан с B), а {A, B, C} определенно не существует, так как C не имеет отношения ни к кому. {A}, {B}, {C} - единственное разбиение, которое удовлетворяет моему определению подмножеств отношений.

Гипотеза: Подмножество отношений всегда является соединением сильно связанных компонентов, так что каждая сильносвязанная компонента в объединении имеет хотя бы один элемент, который связан с некоторым элементом в другой сильно связанной компоненте в объединении. Но для этого понадобилось бы математическое доказательство.

Update: Я усилил выше определение соответствующего подмножества (сильно), так что: BinaryPredicate «родственный» должен быть рефлексивный (связаны (х, х) == верно для любого х), симметричный ((x, y) подразумевает связанные (y, x)), а транзитивные (связанные (x, y) и связанные (y, z) влечет связанные (x, z)). Это разбивает любой набор на классы эквивалентности. removeRelated удаляет все элементы из каждого класса эквивалентности, за исключением первого элемента в контейнере. Это обобщает классическую проблему «удалить все дубликаты», поскольку равенство является частным случаем отношения эквивалентности. Следующий код теперь дает правильные результаты, но мне интересно, есть ли способ ослабить условие «родственных» и получить одинаковые результаты.

#include <iostream> 
#include <algorithm> 
#include <list> 
#include <set> 

template<typename Container, typename BinaryPredicate> 
void removeRelated (Container& container, BinaryPredicate related) { 
    using element = typename Container::value_type; 
    std::set<element> s; 
    for (typename Container::iterator it = std::begin(container); it != std::end(container);) { 
     if (std::find_if(s.begin(), s.end(), 
       [=](const element& x)->bool {return related(*it,x);}) != s.end()) 
      it = container.erase(it); // *it is related to an element in s. 
     else { 
      s.insert(*it); 
      it++; 
     } 
    } 
} 

// Used for testing removeRelated. Person::isRelativeOf is an equivalence relation. 
struct Person { 
    std::string name; 
    std::list<Person*> relatives; 
    Person (const std::string& n) : name(n) {relatives.push_back(this);} // Forcing reflexivity 
    void addRelative (Person* p) { 
     for (Person* relatives_of_p : p->relatives) 
      relatives.push_back(relatives_of_p); // Forcing transitivity ('relatives.push_back(p);' included in this) 
     p->relatives.push_back(this); // Forcing symmetry 
    } 
    bool isRelativeOf (Person* p) const { 
     return std::find(relatives.begin(), relatives.end(), p) != relatives.end(); 
    } 
}; 

int main() { 
    Person *bob = new Person("Bob"), *mary = new Person("Mary"), *jim = new Person("Jim"), 
     *sally = new Person("Sally"), *fred = new Person("Fred"); 
    bob->addRelative(mary); // crashes 
    mary->addRelative(jim); 
    jim->addRelative(bob); 
    sally->addRelative(fred); 
    std::list<Person*> everybody {bob, mary, jim, sally, fred}; 
    removeRelated (everybody, [](Person* a, Person* b)->bool {return a->isRelativeOf(b);}); 
    for (const Person* x : everybody) std::cout << x->name << ' '; // Bob Sally (correct) 
} 

Если «связаны» есть «знает» или «дружит», которые не должны быть симметричны, ни транзитивным, будет у нас еще есть разделение и, таким образом, removeRelated может еще работать?

И еще один вопрос, о котором я спрашиваю: какой самый быстрый алгоритм сортировки сортирует выше, чтобы классы эквивалентности состояли из последовательных элементов? Это то, что я придумал:

template<typename Container, typename BinaryPredicate> 
void sortByEquivalenceClasses (Container& container, BinaryPredicate related) { 
    for (auto it = container.begin(); it != container.end(); ++it) 
     for (auto jt = std::next(it); jt != container.end(); ++jt) 
      if (related(*it, *jt)) { 
       std::iter_swap(jt, std::next(it)); 
       break; 
      } 
} 

Но сортировка не сохраняет первоначальный относительный порядок элементов. Как это сохранить?

Answer 1

Хорошо, можно определить подмножество следующим

Определим «отношение подмножество» как совокупность всех элементов таким образом, что любой элемент в подгруппе связано, по меньшей мере, одного другого элемента в подмножество с помощью «связанных», кроме себя

Этот звук немного рекурсивной, но как я понимаю

• узел n без исходящего г элации находятся в подмножестве, который является одноэлементным {n}
• Узла n, который имеет исходящие отношения только синглетоны, находятся в подмножестве, который является одноэлементным {n}
• Любого цикла (любой длиной), а в более общем случае любые сильно связаны компонент формирует подмножество, , включая все их предшествующие узлы для отношения.

Пример. Имеют место следующие соотношения:

A -> B 
B -> A 
C -> B 
D -> C 
E -> F 

Определим следующие подмножества: {A, B, C, D}, {E} и {F}

---

Учитывая вышеизложенное является правильным, мы можем разработать следующий алгоритм (псевдокод):

int visit(Node n, int s) { // returns 0 iff there is no cycle anywhere beneath 

    if(length(n.relations) = 0 || n.singleton == true) 
    // leaves, or only leaves below 
    { 
     n.singleton = true; 
     return false; 
    } 
    else if(n.visited == true || n.bigger_subset > 0) 
    // part of a subcycle, or predecessor of one 
    { 
     n.bigger_subset = s; 
     return true; 
    } 
    else 
    // searching for the nature of what is below 
    { 
     n.visited = true; 
     bool found_cycle = 0; 

     for each node m such that n is related to m (n -> m) 
      found_cycle = max(Visit(m), found_cycle); 

     if(found_cycle > 0) 
      n.bigger_subset = found_cycle; 
     else 
      n.singleton = true; // parent of only singletons 

     n.visited = false; 
     return found_cycle; 
    } 
} 

s = length(node_set) + 1; // clearly bigger than the maximal number of subsets 
for n in node_set: 
{ 
    if(n.singleton == false && n.big_subcycle == 0) 
    { 
     // state unknown, it is thus the first of its subset, unless it is a predecessor (or part) of a known subset 
     int set = visit(n, s); 

     // not a singleton, and not the current set : a previous one 
     if(set > s) 
      node_set.remove(n); 

     s--; 
    } 
    else 
     node_set.remove(n); 
} 

Что это такое - это в основном поиск по глубине из каждого элемента, маркировка узлов, которые посещаются, чтобы определить циклов ect. Помня о состоянии каждого узла, любой предшественник подмножества может быть добавлен в подмножество, не возвращаясь к циклу снова.

---

Вот код С для этого алгоритма на примере, приведенном выше: http://ideone.com/VNumcN