《数据结构、算法与应用C++语言描述》-栈的应用-离线等价类问题

完整可运行代码见：Github::Data-Structures-Algorithms-and-Applications/_12Offline_equivalence_class_problem/

离线等价类问题

问题描述

等价类：假定一个具有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]
1
2
3
4
5
6
7
8
9

在第二个阶段是寻找等价类。为寻找一个等价类，首先要找到该等价类中第一个没有输出的元素。这个元素作为该等价类的种子。该种子作为等价类的第一个成员输出。从这个种子开始，我们找出该等价类的所有其他成员。种子被加到一个表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 
#include 
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 input
        cout << "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 input
            cout << "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 input
        cout << "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 input
            cout << "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 input
            cout << "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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

运行结果

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21