令related为二进制谓词。让我们将“关系子集”定义为所有元素的集合，以使子集中的任何元素都通过“相关”与子集中的至少一个其他元素相关联，而不是自身(因此，一个元素是否与其自身相关或与形成关系子集无关)。注意:关系子集不一定是strongly connected component。例如，假设A与B相关，并且B和C彼此相关。然后，{A，B，C}从定义上讲是一个关系子集，但不是牢固连接的组件，因为没有从B到A或从C到A的经由“相关”的路径。
请注意，“相关”并不一定是对称的，即related(a，b)== true不一定意味着related(b，a)== true，也不是可传递的，即related(a，b)== true和related(b，c)== true并不一定意味着related(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.
在此示例中，当且仅当A知道B时，A才与B相关。{Bob，Mary，Jim}是一个关系子集，因为每个人都与其他人相关(Bob与Mary相关，Mary与Jim，Jim相关与鲍勃有关)。请注意，{Sally，Fred}不是关系子集，因为尽管Sally与Fred有关，但Fred与Sally没有关系。因此，我们剩下{Sally}，{Fred}作为其他两个关系子集。
所以最后的答案应该是:鲍勃，莎莉，弗雷德。请注意，如果要定义函数
partition，则它将简单地保留{Bob，Mary，Jim，Sally，Fred}不变，而Bob，Sally和Fred是每个分区的第一个元素。因此，即使我们具有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.
}
上面代码的错误是Mary插入到s中，因为那时她与s中的任何人都不相关(通过“知道”)。最后，她与吉姆(Jim)有关系，吉姆(Job)通过“知道”与鲍勃(以及鲍勃(Bob)到玛丽(Mary))相关，因此{Bob，Mary，Jim}是一个关系子集，因此bob应该是这三个中的唯一一个人们在“s”。
但是在迭代过程中，函数不知道这一点。如何修复算法？
一个想法可能是首先定义上述函数
partition，即对容器进行排序，以便将容器划分为其关系子集(这本身是一个非常好的问题，并且很可能是当前的主要问题)，然后简单地取每个分区的第一个元素。另一个想法是替换lambda函数
[=](const element& x)->bool {return related(*it,x);}
与
[=](const element& x)->bool {return relatedIndirectly(*it,x);}
我认为这可能会解决问题，其中与助手功能相关的间接搜索与x的关系链。
这是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}是满足我对关系子集的定义的唯一分区。
猜想:关系子集始终是强连接的组件的并集，这样，该并集中的每个强连接的组件都具有至少一个与该并集中不同的强连接的组件中的某个元素相关的元素。但这需要数学证明。
更新:
我加强了对相关子集的上述定义，从而:
BinaryPredicate'related'应该是自反的(related(x，x)==对于任何x都是true)，对称的(related(x，y)暗示related(y，x))和可传递的(related(x，y)和related (y，z)暗示related(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)
}
如果“相关”是“知道”或"is"的 friend ，而不必对称或可传递，那么我们是否还会有一个分区，从而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;
}
}
但是排序不会保留元素的原始相对顺序。如何保存呢？
最佳答案
好的，您可以通过以下方式定义一个子集
听起来有点递归，但是据我了解
n {n} n仅与单例具有传出关系。例。以下关系:
A -> B
B -> A
C -> B
D -> C
E -> F
定义以下子集:
{n}，{A, B, C, D}和{E}假设以上正确，我们可以设计以下算法(伪代码):
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);
}
基本上，这是从每个元素开始的深度优先搜索，标记要访问的节点，以便检测周期。通过记住每个节点的状态，子集的任何前任都可以添加到该子集，而无需再次进入循环。
这是上面给出的示例中该算法的C代码:http://ideone.com/VNumcN
关于c++ - “remove all duplicates”的推广，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27233367/