Тест на симметрию в отношении с использованием наборов

Question

Я работаю с упорядоченными парами типа unsigned 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

Ваша логика зацикливания полностью испорчена.

Внутреннее время не меняет ни it3, ни it4.Так что либо он вернет 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; 
}

Демонстрация в Интернете

Существует даже более прохладное решение, если вам разрешено использовать библиотеку алгоритмов:

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();}) ;
}

Демо-версия 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();}) ;
}

Онлайн-демонстрация 3 (с длинной без знака)