离线等价类问题

问题描述

等价类：假定一个具有n个元素的集合U=1，2，…，n和一个具有r个关系的集合$R=（i_1，j_1），（i_2，j_2），\dots ，（i_r,j_r）$。关系 R是一个等价关系（equivalence relation），当且仅当如下条件为真：

• 对于所有的$a\subset R$，有（a，a）$\subset$R时（关系是自反的）。
• （a，b）$\subset$R，当且仅当（b，a）$\subset$R（关系是对称的）。
• 若（a，b）$\subset$R且（b，c）$\subset$R，则有（a，c）$\subset$R（关系是传递的）。

在给出等价关系R时，我们经常会忽略其中的某些数对，这些数对可以应用等价关系的自反性、对称性和传递性来得到。

如果（a，b）$\subset$R，则元素a和b是等价的。所谓等价类（equivalence class）是指相互等价的元素的最大集合。“最大”意味着不存在类以外的元素与类内部的元素等价。因为一个元素只能属于一个等价类，等价关系把集合 U划分为不相交的等价类。

举例

例6-3 假定 n=14，R={（1，11），（7，11），（2，12），（12，8），（11，12），（3，13），（4，13），（13，14），（14，9），（5，14），（6，10）}。我们忽略了所有形如（a，a）的数对，因为按照自反性，这些数对是隐含的。同样也忽略了所有对称的数对。因为（1，11）$\subset$R，所以按照对称性应有（11，1）$\subset$R。其他被忽略的数对由传递性可以得到。例如，由（7，11）和（11，12），可以得到（7，12）$\subset$R。

例 6-4 考察例 6-3 中的等价关系。由于元素 1 与 11，11 与 12 是等价的，因此，元素1、11、12是等价的，它们应属于同一个等价类。不过，这三个元素还不能构成一个等价类，因为还有其他的元素与它们等价（例如7）。因此（1，11，12）不是等价元素的最大集合。集合{1，2，7，8，11，12）才是一个等价类。关系R还定义了另外两个等价类：（3，4，5，9，13，14）和（6，10）。注意，这三个等价类是互不相交的。

在离线等价类（offline equiralence class）问题中，已知 n 和 R，确定所有的等价类。由等价类的定义得知，每个元素只能属于一个等价类。
简化问题描述：这个问题的输入是元素数目n、关系对数目r以及r个关系对。目标是把n个元素划分为等价类。

求解策略

求解分为两个阶段。在第一个阶段，我们输入数据，建立 n个表以表示关系对。对每一个关系对（i，j），i放在list[j]，j放在list[i]。

例8-3 假定n=9，r=11，且11个关系对是（1，5），（1.6），（3，7），（4，8），（5，2），（6，5），（4，9），（9，7），（7，8），（3，4），（6，2）。9个表是：

list[1]=[5，6]
list[2]=[5,6]
list[3]=[7,4]
list[4]=[8,9,3]
list[5]=[1,2,6]
list[6]=[1,2,5]
list[7]=[3,9,8]
lis[8]=[4,7]
list[9]=[4,7]

在第二个阶段是寻找等价类。为寻找一个等价类，首先要找到该等价类中第一个没有输出的元素。这个元素作为该等价类的种子。该种子作为等价类的第一个成员输出。从这个种子开始，我们找出该等价类的所有其他成员。种子被加到一个表unprocessedList中。从表unprocessedLis中删除一个元素i，然后处理表list[i]。list[i]中所有元素和种子同属一个等价类；将list[i]中还没有作为等价类成员的元素输出，然后加入unprocessedList中。这是一个过程：从表 unprocessedLis 中删除一个元素i，然后把表 list[i]中还没有输出的元素输出，并且加入unprocessedList中。这个过程持续进行到unprocessedList为空。这时我们就找到了一个等价类，然后继续寻找下一个等价类的种子。

例8-4 考虑例8-3。令1 是第一个种子，作为一个等价类的成员被输出，然后加入表unprocessedList中。接下来把1从unprocessedList中删除，然后处理list[1]。元素5和6属于list[1]，与1同属一个等价类，它们被输出，然后加入unprocessedList中。将5或6从unprocessedList中删除，然后处理它们所在的表。假定删除的是5。考察list[5]中的元素1、2和6。因为1和6已经输出，所以被忽略。把元素2输出，然后加入unprocessedList中。当unprocessedList中的剩余元素（6和2）被删除和处理，没有其他元素被输出或加入unprocessedList时，unprocessedList成为空表，这时我们便找到了一个等价类。
为找到另一个等价类，我们要寻找一个种子，它是还没有输出的元素。元素 3 还没有输出，因此可以作为下一个等价类得种子。元素3、4、7、8和9作为这个等价类的元素被输出。这时不再有种子，因此我们找到了所有等价类。

代码

#include <iostream>
#include <stack>
using namespace std;/*离线等价类问题*/
void offlineEquivalenceClass()
{int n,//元素个数r;//关系个数/*输入元素个数n*//*首先成功输入一次*/cout << "Enter number of elements(n >= 2):";while (!(cin >> n)) {//如果输入类型不匹配，则执行循环体cin.clear(); // reset input设置标志位为有效while (cin.get() != '\n') //删除没有用的输入continue; // get rid of bad inputcout << "Enter number of elements(n >= 2):";}/*成功输入一次后检查是否符合要求*/while (n < 2) {//如果元素个数小于2，则出错cout << "n must be equal or bigger than 2!" << endl;cout << "Enter number of elements(n >= 2):";while (!(cin >> n)) {//如果输入类型不匹配，则执行循环体cin.clear(); // reset input设置标志位为有效while (cin.get() != '\n') //删除没有用的输入continue; // get rid of bad inputcout << "Enter number of elements(n >= 2):";}}/*输入关系个数r*//*首先成功输入一次*/cout << "Enter number of relations(r >= 1):";while (!(cin >> r)) {//如果输入类型不匹配，则执行循环体cin.clear(); // reset input设置标志位为有效while (cin.get() != '\n') //删除没有用的输入continue; // get rid of bad inputcout << "Enter number of relations(r >= 1):";}/*成功输入一次后检查是否符合要求*/while (r < 1) {//如果元素个数小于2，则出错cout << "r must be equal or bigger than 1!" << endl;cout << "Enter number of relations(r >= 1):";while (!(cin >> r)) {//如果输入类型不匹配，则执行循环体cin.clear(); // reset input设置标志位为有效while (cin.get() != '\n') //删除没有用的输入continue; // get rid of bad inputcout << "Enter number of relations(r >= 1):";}}/*建立空栈组成的数组，stack[0]不用，用于存储表格*/stack<int>* list = new stack<int>[n + 1];/*输入r个关系，存储在表中*/int a, b;//(a,b)是一个关系for (int i = 1; i <= r; i++){cout << "Enter next relation/pair:";while (!(cin >> a >> b)) {//如果输入类型不匹配，则执行循环体cin.clear(); // reset input设置标志位为有效while (cin.get() != '\n') //删除没有用的输入continue; // get rid of bad inputcout << "Enter error!Enter current relation/pair:";}list[a].push(b);list[b].push(a);}/*初始化已输出等价类*/stack<int> unprossedList;bool* out = new bool[n + 1];//判断该元素是否输出for (int i = 1; i <= n; i++)out[i] = false;/*输出等价类*/for (int i = 1; i <= n; i++){if (!out[i]){cout << "Next class is:" << i << " ";out[i] = true;unprossedList.push(i);//从unprossedList中取类的剩余元素while (!unprossedList.empty()){int j = unprossedList.top();unprossedList.pop();while (!list[j].empty()){int q = list[j].top();list[j].pop();if (!out[q]) //未输出{cout << q << " ";out[q] = true;unprossedList.push(q);}}}cout << endl;}}cout << "End of list of eqivalence classes." << endl;
}int main()
{cout << "offlineEquivalenceClass()*******" << endl;offlineEquivalenceClass();return 0;
}

运行结果

C:\Users\15495\Documents\Jasmine\Work\coding\cmake-build-debug\coding.exe
offlineEquivalenceClass()*******
Enter number of elements(n >= 2):14
Enter number of relations(r >= 1):11
Enter next relation/pair:1 11
Enter next relation/pair:7 11
Enter next relation/pair:2 12
Enter next relation/pair:12 8
Enter next relation/pair:11 12
Enter next relation/pair:3 13
Enter next relation/pair:4 13
Enter next relation/pair:13 14
Enter next relation/pair:14 9
Enter next relation/pair:5 14
Enter next relation/pair:6 10
Next class is:1 11 12 7 8 2 
Next class is:3 13 14 4 5 9
Next class is:6 10
End of list of eqivalence classes.Process finished with exit code 0