离散数学实验：集合关系的二元性质判定

使用c++语言实现，用multimap来表示随机生成的集合关系(如<a,a>)

//
// Created by 徐昊岩 on 2023/11/17.
//
#include "iostream"
#include "ctime"
#include "cstdlib"
#include "set"
#include "vector"
#include "map"
#include "cmath"
#include "algorithm"

using namespace std;

//判断目标键值对keyToFind:valueToFind是否位于multimap中
bool is_in_map(multimap<char, char> myMultiMap, char keyToFind, char valueToFind) {
    auto range = myMultiMap.equal_range(keyToFind);  //equal_range返回一个键均为key的范围，且以pair类型组织首个迭代器和末尾迭代器
    for (auto it = range.first; it != range.second; ++it) {
        if (it->second == valueToFind) {
            return true;
        }
    }
    return false;
}

int main() {
    set<char> set1;  //创建集合，用来存储输入的集合元素
    char a;
    cout << "please input elements of the set(end with @):" << endl;
    while (true) {
        cin >> a;
        if (a == '@') break;
        set1.emplace(a);  //将读入元素存到集合中
    }
    srand(time(0));   //设定随机数种子
    int num = rand() % (int) (pow(2, set1.size())) + 1;  //随机生成某个关系的总数(大小为1到2的n次方)
    multimap<char, char> map1;       //建立散列表存储生成的关系
    vector<char> vector_all(set1.begin(), set1.end());  //将集合转为动态数组，方便取索引
    vector<int> value_count(set1.size(), 0);   //由于一个键只有n种关系，创建数组用以存储某个键已经产生的关系总数，避免关系重复生成
    //生成一种随机关系
    for (int i = 0; i < num; i++) {
        int t_rand1 = rand() % vector_all.size();
        int t_rand2 = value_count[t_rand1]++;
        if (t_rand2 >= set1.size()) { continue; }
        map1.emplace(vector_all[t_rand1], vector_all[t_rand2]);
    }
    //显示出生成的随机关系
    cout << "Generate Relationship Set:" << endl << "{";
    for (pair<char, char> pair: map1) {
        cout << "<" << pair.first << "," << pair.second << ">" << " ";
    }
    cout << "}\n";

    //判断自反性/反自反性
    int reflex_count = 0;
    for (pair<char, char> pair: map1) {
        if (pair.first == pair.second) reflex_count += 1;
    }
    if (reflex_count == 0) cout << "satisfy anti-reflexive relation" << endl;
    else if (reflex_count == set1.size()) cout << "satisfy reflexive relation" << endl;
    else cout << "doesn't satisfy reflexive/anti-reflexive relation" << endl;

    //判断对称性/反对称性
    multimap<char, char> map1_swap; //multimap是有序的,创建另一个multimap用来存储交换后的键值对
    for (pair<char, char> pair: map1) {
        map1_swap.emplace(pair.second, pair.first);  //交换每个pair的键值对
    }

    if (includes(map1.begin(), map1.end(), map1_swap.begin(),
                 map1_swap.end())) { //algorithm中的includes方法可以判断有序数据结构1是否包含同类型有序数据结构2，返回1或0,还可以用来判断两个有序数据结构是否相等
        cout << "satisfy symmetry relation" << endl;
    } else cout << "doesn't satisfy symmetry relation" << endl;

    multimap<char, char> map2_delete_same;  //创建一个multimap删去键值对相等的关系,例如<a,a>
    multimap<char, char> map2_delete_same_swap;
    for (pair<char, char> pair: map1) {
        if (pair.first == pair.second) continue;    //键值对相等的去掉，方便比较反对称性
        map2_delete_same.emplace(pair.first, pair.second);
        map2_delete_same_swap.emplace(pair.second, pair.first);
    }

    if (includes(map2_delete_same.begin(), map2_delete_same.end(), map2_delete_same_swap.begin(),
                 map2_delete_same_swap.end()) == 0) {
        cout << "satisfy anti-symmetry relation" << endl;
    } else cout << "doesn't satisfy anti-symmetry relation" << endl;


    //判断传递性
    bool istransitivity = true;  //默认传递性为真
    for (pair<char, char> pair: map1) {
        auto ranges = map1.equal_range(pair.second);  //获得某个键(例如a)开头关系对应的所有后域(<a,a>就是a;<a,b>就是b....)
        for (auto it = ranges.first; it != ranges.second; it++) {    //遍历所有b开头的关系
            if (!is_in_map(map1, pair.first, it->second)) {   //找前域为b关系的每个后域c，再看<a,c>是否在map中，以此判断传递性
                istransitivity = false;
                break;
            }
        }
    }
    if (istransitivity) cout << "satisfy transitive relation" << endl;
    else cout << "doesn't satisfy transitive relation" << endl;
}