使用集合测试关系的对称性

Question

我正在使用无符号类型的有序对 typedef pair<unsigned, unsigned> OP; 和有序对集 typedef set<OP> SOP;.

我程序的最终目标是检查集合（关系）是否为等价关系。

我的问题：我已经设法检查集合是否自反，但目前我正在尝试检查集合（关系）中的有序对是否对称。我目前构建了两个 for 循环来比较有序对，但在我的比较中遇到了死胡同。

我的代码：

for (auto it3 = sop.begin(); it3 != sop.end(); it3++) { // loop through each pair in set
        for (auto it4 = sop.begin(); it4 != sop.end(); it4++) { // compare with other pairs
           // make sure first and second items in pair are different
            while (it3->first != it3->second) {
               //If the case is that there is not an instance of 
               //symmetric relation return false  
                if (!((it3->first == it4->second) && (it3->second == it4->first))) {
                    return false;
                }
            }
        }
    }

Answer 1

你的循环逻辑完全有问题。

内部 while 既不改变 it3 也不改变 it4。所以它要么 return false 要么永远循环。此外，内部 for 循环并没有利用集合是有序的这一事实。

你要的测试就简单多了

在 sop 上循环就足够了，并检查每个项目是否也在集合中。如果一个不是，则不是对称关系。如果都成功找到反面就好了：

bool is_symetric (SOP sop) {
    for (auto it3 = sop.begin(); it3 != sop.end(); it3++) { // loop through each pair in set
        if (it3->first != it3->second) {
            if (sop.find({it3->second,it3->first })==sop.end()) {
                return false;
            }
        }
    }
    return true; 
}

Online demo

如果允许使用算法库，还有更酷的解决方案：

bool is_symetric (SOP sop) {
    return all_of(sop.cbegin(), sop.cend(),
        [&sop](auto &x){ return x.first==x.second || sop.find({x.second,x.first })!=sop.end();}) ;
}

Online demo 2

更酷的是，如果您将其设为模板，不仅可以使用无符号类型，还可以使用任何其他类型：

template <class T>
bool is_symetric (set<pair<T,T>> sop) {
    return all_of(sop.cbegin(), sop.cend(),
        [&sop](auto &x){ return x.first==x.second || sop.find({x.second,x.first })!=sop.end();}) ;
}

Online demo 3 (with unsigned long long)

使用集合测试关系的对称性

Test for symmetry in relation using sets

c++

algorithm

set

relationship

discrete-mathematics