title: Generalization of "remove all duplicates"
body: <p>Let <code>related</code> be a binary predicate.  Let us define a "relation subset" as the set of all elements such that any element in the subset is related to at least one other element in the subset via 'related', other than itself (hence whether an element is related to itself or not is irrelevant in forming the relation subsets).  Note:  a relation subset is NOT necessarily a <a href="http://en.wikipedia.org/wiki/Strongly_connected_component" rel="nofollow">strongly connected component</a>.  For example, suppose A is related to B, and B and C are related to each other.  Then {A,B,C} is a relation subset by definition, but is not a strongly connected component because there is no path from B to A or from C to A via 'related'.</p>
  
  <p>Note that 'related' is not necessarily symmetric, i.e. related(a,b) == true does not necessarily mean that related(b,a) == true, nor is it transitive, i.e. related(a,b) == true and related(b,c) == true does not necessarily imply related(a,c) == true.  As far as I can see, no restrictions on the binary predicate <code>related</code> need be imposed in order to partition a set into relation subsets.  If an element x is not related to any element at all (other than itself), then {x} is itself its own relation subset.</p>
  
  <p>One good problem is to define</p>
  
  <pre><code>template &lt;typename Container, typename BinaryPredicate&gt;
  void partition (Container&amp; container, BinaryPredicate related);
  </code></pre>
  
  <p>that will sort the elements of container so that the container is partitioned into its relation subsets.  This question arose quickly after attempting the original problem:</p>
  
  <pre><code>template &lt;typename Container, typename BinaryPredicate&gt;
  void removeRelated (Container&amp; container, BinaryPredicate related);
  </code></pre>
  
  <p>which is to remove (from <code>container</code>) all elements from each relation subset, except for the first one of each subset found in the container.</p>
  
  <p>Of course, equality is just a special case of 'related', and hence this is a generalization of "remove all duplicates" (that is how I thought up this question, by trying to generalize that well-known solved problem).  What we want is to keep one representative of each relation subset, namely the first one according to the container's ordering of elements.</p>
  
  <p>Below is the code I tried to implement, with the following relationships : </p>
  
  <pre><code>Bob knows Mary
  Mary knows Jim
  Jim knows Bob
  Sally knows Fred
  Fred knows no one.
  </code></pre>
  
  <p>In this example, A is related to B if and only if A knows B. {Bob, Mary, Jim} is a relation subset because each person is related to someone else (Bob is related to Mary, Mary is related to Jim, Jim is related to Bob). Note that {Sally, Fred} is NOT a relation subset because though Sally is related to Fred, Fred is not related to Sally. Thus we are left with {Sally}, {Fred} as the other two relation subsets.</p>
  
  <p>So the final answer should be : Bob, Sally, Fred.  Note that if the function <code>partition</code> were to be defined, then it would simply leave {Bob, Mary, Jim, Sally, Fred} unchanged, with Bob, Sally, Fred being the first element of each partition.  Hence even if we had the <code>partition</code> function (not to be confused with std::partition of course, but I'm not really thinking about a good name right now), it is still not immediately clear what <code>removeRelated</code> would need.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;algorithm&gt;
  #include &lt;list&gt;
  #include &lt;set&gt;
  
  template&lt;typename Container, typename BinaryPredicate&gt;
  void removeRelated (Container&amp; container, BinaryPredicate related) {
      using element = typename Container::value_type;
      std::set&lt;element&gt; s;
      for (typename Container::iterator it = std::begin(container);  it != std::end(container); ) {
          if (std::find_if(s.begin(), s.end(),
                  [=](const element&amp; x)-&gt;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&lt;Person*&gt; peopleKnown;
      Person (const std::string&amp; 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-&gt;learnsAbout(mary);
      mary-&gt;learnsAbout(jim);
      jim-&gt;learnsAbout(bob);
      sally-&gt;learnsAbout(fred);
      std::list&lt;Person*&gt; everybody {bob, mary, jim, sally, fred};
      removeRelated (everybody, [](Person* a, Person* b)-&gt;bool {return a-&gt;knows(b);});
      for (const Person* x : everybody) std::cout &lt;&lt; x-&gt;name &lt;&lt; ' ';  // Bob Mary Sally Fred
  //  Should be 'Bob Sally Fred' since {Bob, Mary, Jim}, {Sally}, {Fred} are the relation subsets.
  }
  </code></pre>
  
  <p>The bug from the code above is that Mary is inserted into 's' because at that point she is not related to anyone in s (through 'knows'). In the end, she is related to Jim, who is related to Bob (and Bob to Mary) through 'knows', and hence {Bob, Mary, Jim} is a relation subset, so bob should be the only one of these three people in 's'.</p>
  
  <p>But during the iteration the function does not know that. How can I fix the algorithm?
  One idea is to perhaps first define the function <code>partition</code> mentioned above, i.e. to sort the container so that the container is partitioned into its relation subsets (which is a very nice problem in itself, and could very well be the main question at hand), and then simply take the first element of each partition.</p>
  
  <p>Another idea is to replace the lambda function</p>
  
  <pre><code>[=](const element&amp; x)-&gt;bool {return related(*it,x);}
  </code></pre>
  
  <p>with</p>
  
  <pre><code>[=](const element&amp; x)-&gt;bool {return relatedIndirectly(*it,x);}
  </code></pre>
  
  <p>and I think it might solve the problem, where the helper function relatedIndirectly searches for a chain of relations to x.</p>
  
  <p>Here is another example examined by Cimbali (below).  Suppose A is related to B, A is related to C, B is related to C.  Then {A,B} cannot be a relation subset because B is not related to A.
  Similarly, {A,C} and {B,C} cannot be relation subsets (C is not related to A, and C is not related to B), and {A,B,C} definitely not since C is not related to anyone.
  {A}, {B}, {C} is the only partitioning that satisfies my definition of relation subsets.</p>
  
  <p>Conjecture: A relation subset is always the union of strongly connected components such that each strongly connected component in the union has at least one element that is related to some element in a different strongly connected component in the union.  But this would need mathematical proof.</p>
  
  <p><strong>Update:</strong>
  I've strengthened the above definition of related subset (greatly) so that:
  BinaryPredicate 'related' shall be reflexive (related(x,x) == true for any x), symmetric (related(x,y) implies related(y,x)), and transitive (related(x,y) and related(y,z) implies related(x,z)).  This partitions any set into equivalence classes.  removeRelated shall remove all elements from every equivalence class except for the first element in the container.  This generalizes the classic problem of "remove all duplicates", since equality is a special case of an equivalence relation.  The following code now gives the correct results, but I wonder if there is a way to weaken the condition of 'related' and still get the same results.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;algorithm&gt;
  #include &lt;list&gt;
  #include &lt;set&gt;
  
  template&lt;typename Container, typename BinaryPredicate&gt;
  void removeRelated (Container&amp; container, BinaryPredicate related) {
      using element = typename Container::value_type;
      std::set&lt;element&gt; s;
      for (typename Container::iterator it = std::begin(container);  it != std::end(container); ) {
          if (std::find_if(s.begin(), s.end(),
                  [=](const element&amp; x)-&gt;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&lt;Person*&gt; relatives;
      Person (const std::string&amp; n) : name(n) {relatives.push_back(this);}  // Forcing reflexivity
      void addRelative (Person* p) {
          for (Person* relatives_of_p : p-&gt;relatives)
              relatives.push_back(relatives_of_p);  // Forcing transitivity ('relatives.push_back(p);' included in this)
          p-&gt;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-&gt;addRelative(mary);  // crashes
      mary-&gt;addRelative(jim);
      jim-&gt;addRelative(bob);
      sally-&gt;addRelative(fred);
      std::list&lt;Person*&gt; everybody {bob, mary, jim, sally, fred};
      removeRelated (everybody, [](Person* a, Person* b)-&gt;bool {return a-&gt;isRelativeOf(b);});
      for (const Person* x : everybody) std::cout &lt;&lt; x-&gt;name &lt;&lt; ' ';  // Bob Sally (correct)
  }
  </code></pre>
  
  <p>If 'related' is 'knows' or 'is friends of', which need not be symmetric nor transitive, will we still have a partitioning and thus removeRelated can still work?</p>
  
  <p>And another question I wonder about is:  what is the fastest sorting algorithm to sort the above so that the equivalence classes consist of consecutive elements?  This is what I came up with:</p>
  
  <pre><code>template&lt;typename Container, typename BinaryPredicate&gt;
  void sortByEquivalenceClasses (Container&amp; 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;
              }
  }
  </code></pre>
  
  <p>But the sort does not preserve the original relative ordering of the elements.  How to preserve that?</p>