c++ - 如何测试一个集合是否自反、对称、反对称和/或传递？

Question

我在尝试编写这些函数时遇到困难。他们工作不正常，不知道我做错了什么。至于 Transitive，我什至无法开始，希望你能提供任何帮助，以及我在我的功能中做错了什么。谢谢。
示例输入:

0 1 2 3 //elements (A)
0 0     //relations (B)
1 1
2 2
3 3

x y z //elements (A)
x y   //relations (B)
y z
y y
z z

x y z //elements (A)
x x   //relations (B)
y z
x y
z y
x z
y y
z x
y x
z z

1 2 3 4 5 6 7 8 //elements (A)
1 4             //relations (B)
1 7
2 5
2 8
3 6
4 7
5 8
6 6
1 1
2 2

代码:

bool reflexive(int a[], int sizeOfA, int b[], int sizeOfB) 
{
  bool hold = true;
  for(int i=0; i+1<sizeOfB; i+=2) 
  {
    int e = b[i];
    int e1 = b[i];
    if(pair_is_in_relation(e1, e, b, sizeOfB) == false) 
    {
        if (hold) 
    {
            return false;
            break;
         }
    }
  }
  if (hold)
    cout << "Reflexive - Yes" << endl; 
  else
    cout << "Reflexive - No" << endl; 
return hold;
}

bool symmetric(int a[], int sizeOfA, int b[], int sizeOfB)
{
bool hold = true; // set hold to true
for(int i=0; i+1<sizeOfB; i+=2) // for each pair (e,f) in b
{
    int e = b[i];
    int f = b[i+1];
    if(is_in_relation(f, e, b, sizeOfB)) // if pair(e,f) is not in b
    {
        if(hold) // set hold to false
        {
            return false;
            break;
        }
    }
}
if(hold) // if hold return true
    cout << "Symmetric - Yes" << endl;
else // if hold is false return false
    cout << "Symmetric - No" << endl;
}

void antiSymmetric(int b[], int sizeOfB)
{
bool hold = true; // set hold to true
for(int i = 0; i < sizeOfB;) // for each pair (e,f) in b
{
    if(hold == false)
    {
        cout << "AntiSymmetric - No" << endl; 
        break; //Did not find (e,e) in b
    }
    for(int j = 0; j < sizeOfB;)
    {
        if(b[i] == b[j+1] && b[i+1] == b[j]) //If true, then pair(f,e) exists
        {
            if(b[i+1] != b[i]) //If true, relation is antisymmetric
            {
                hold = true;
                break;
            }
            else
            {
                hold = false;
                j = j + 2;
            }
        }
        else
        {
            hold = false;
            j = j + 2;
        }

    }
    i = i + 2;

}
if(hold == true)
    cout << "AntiSymmetric - Yes" << endl;

}

void transitive(int a[], int sizeOfA, int b[], int sizeOfB)
{

}

int main()
{
char keepGoing = 'y';
    while (keepGoing=='y') {

int set1[4] = {0, 1, 2, 3};
int rel1[8] = {0, 0, 1, 1, 2, 2, 3, 3};
cout << "Set 1: " << endl;
reflexive(set1, 3, rel1, 4);
symmetric(set1, 3, rel1, 4);
antiSymmetric(set1, 3, rel1, 4);

cout << endl;
char set2[4] = {'x', 'y', 'z'};
char rel2[8] = {'x', 'y', 'y', 'z', 'y', 'y', 'z', 'z'};
cout << "Set 2: " << endl;
charReflexive(set2, 4, rel2, 8);
charSymmetric(set2, 4, rel2, 8);
charAntiSymmetric(set2, 4, rel2, 8);

cout << endl;
char set3[3] = {'x', 'y', 'z'};
char rel3[18] = {'x', 'x', 'y', 'z', 'x', 'y', 'z', 'y', 'x', 
                 'z', 'y', 'y', 'z', 'x', 'y', 'x', 'z', 'z'};
cout << "Set 3: " << endl;
charReflexive(set3, 3, rel3, 18);
charSymmetric(set3, 3, rel3, 18);
charAntiSymmetric(set3, 3, rel3, 18);

cout << endl;
int set4[8] = {1, 2, 3, 4, 5, 6, 7, 8};
int rel4[20] = {1, 7, 2, 5, 2, 8, 3, 6, 4, 7, 5, 8, 6, 6, 1, 1,
                2, 2};
cout << "Set 4: " << endl;
reflexive(set4, 8, rel4, 20);
symmetric(set4, 8, rel4, 20);
antiSymmetric(set4, 8, rel4, 20);

cout << endl << "Would you like to test it again? (y/n): ";
    cin >> keepGoing;
}

return 0;
}

Answer 1

我只读过reflexive，但你需要重新考虑一下。通常，如果 A 中的第一个元素不等于 B 中的第一个元素，它会打印 "Reflexive - No" 并停止。我不认为你一直都这么想。

[编辑] 好吧，现在我们终于确定了 int a[] 和 int b[] 的内容，我必须重新开始。每个人之前的想法都是完全错误的。 (尤其是我，我以前的“自反”确实是对称的，并且错误地解释了输入。)如果您了解 C++ 类/容器，我强烈建议替换 int a[] 和int b[] 类似:

template <class T>
struct relation {
    typedef std::pair<T,T> single_relation;

    std::set<T> elements;
    std::set<single_relation> all_relations;
};

或类似的东西，但那只是我。

reflexive:
    set holds to true
    for each element e in a
        if pair(e,e) is not in b
            set holds to false
            break
symmetric:
    set holds to true
    for each pair(e,f) in b
        if pair(f,e) is not in b
            set holds to false
            break
antisymetric: 
    set holds to true
    for each pair(e,f) in b
        if pair(f,e) is in b
            if f is not e
                set holds to false
                break
transitive:
    set holds to true
    for each pair(e,f) in b
        for each pair(f,g) in b
            if pair(e,g) is not in b
                set holds to false
                break
        if holds is false
            break

请注意，只有自反实际上根本需要 a[]。
演示:

bool pair_is_in_relation(int left, int right, int b[], int sizeOfB)
{
    for(int i=0; i+1<sizeOfB; i+=2) {
        if (b[i]==left && b[i+1]==right)
            return true;
    }
    return false;
}
bool antiSymmetric(int b[], int sizeOfB) 
{
    bool holds = true;
    for(int i=0; i+1<sizeOfB; i+=2) {
        int e = b[i];
        int f = b[i+1];
        if(pair_is_in_relation(f, e, b, sizeOfB)) {
            if (e != f) {
                holds = false;
                break;
             }
        }
    }
    if (holds)
        std::cout << "AntiSymmetric - Yes" << endl; 
    else
        std::cout << "AntiSymmetric - No" << endl; 
    return holds;
}