/
matchAlgorithm.cpp
183 lines (154 loc) · 5.91 KB
/
matchAlgorithm.cpp
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
#include "definition.h"
#include "matchAlgorithmTools.h"
#include "matchAlgorithm.h"
using namespace std;
extern students student[310];
extern departments department[25];
extern addmitted addmitted_department[25];
struct student_sorted_t {
int index;
int value;
};
student_sorted_t student_sorted[310];
bool cmp(student_sorted_t &student_instance1, student_sorted_t student_instance2) {
return student_instance1.value > student_instance2.value;
}
void matchAlgorithm::algorithm() {
matchAlgorithmTools algorithmTool;
// deliver the students to the two classes
algorithmTool.deliverStudent();
/*
* The following codes are used to:
*
* 1.update studentWishes to calculate the order among departments.
*
* 2.calculate studentDepValues(student vs department) to find out
* that if the student is matched against the department or not.
* And for the following codes(i.e.L79), the studentDepValues is
* used to help the department choose students.
*
*/
for (int i = 0; i < algorithmTool.eagerStudentNumber; i++) {
// current index of eagerStudents
int currentStudent = i;
// the total number of departments that chosen by the current student
int depTotal = algorithmTool.eagerStudent[currentStudent].applications_department_number;
// j: the number of departments
// k: the number of student wishes
// for each of the departments
for (int j = 0; j < 20; j++) {
int currentDepartment = j;
// the number of current department
string currentDepartment_str = department[currentDepartment].department_number;
// check if the department is the chosen one or not
for (int k = 0; k < depTotal; k++) {
// the k wish of current student
string kwish = algorithmTool.eagerStudent[currentStudent].applications_department[k];
// if matched, means student "py" department
if (kwish == currentDepartment_str) {
// add 1 to studentWishes[department_number: currentDepartment][wishes: k]
algorithmTool.studentWishes[currentDepartment][k]++;
// calculate the value between current student and current department
// based on k(the current number of wishes) and the student instance
// and the department instance
int stuDepValue = algorithmTool.matchedLevelValue(k, algorithmTool.eagerStudent[currentStudent], department[currentDepartment]);
assert(stuDepValue != -1);
// record the stuDepValue calculated by matchedLevelValue(...)
// in studentDepValues[student_instance_index][department_instance_index]
algorithmTool.studentDepValues[currentStudent][currentDepartment] = stuDepValue;
break;
}
}
}
}
/*
* The following codes are used to:
*
* calculate the chosen order among departments,
* eg.department A before department B.
*
* StudentWishes => Order
*
*/
algorithmTool.calculateDepOrder();
/*
* The following codes are used to:
*
* With the order among the departments, we
* select the current department and help
* this department to choose students based
* on the value(student vs currentDepartment).
*
* Then we pick out the unlucky students and
* unlucky departments for outputing JSON
* results.
*
*/
// the total number of departments is 20
for (int i = 0; i < 20; i++) {
// for each of the departments(in turn)
// the index of current department, based on the calculated order
int currentDepartment = algorithmTool.order[i];
// the name of current department
addmitted_department[currentDepartment].department_number = department[currentDepartment].department_number;
// initial the total number of addmitted students
addmitted_department[currentDepartment].number = 0;
// the limitation of current department
int limitation = department[currentDepartment].member_limit;
// sort the students with regard to the values
// for each of the students
for (int j = 0; j < 300; j++) {
// the index of currentStudent
int currentStudent = j;
// the value between currentStudent and currentDepartment
int currentValue = algorithmTool.studentDepValues[currentStudent][currentDepartment];
// at the first time, mark the isChosenByDepartment as false
if (i == 0) {
student[currentStudent].isChosenByDepartment = false;
}
student_sorted[j].index = currentStudent;
student_sorted[j].value = currentValue;
}
// sort the students based on the value(students vs currentDepartment)
sort(student_sorted, student_sorted+310, cmp);
// the current department chooses "limitation"(eg.10-15) students
int k = 0, currentStuIdx = 0;
while (k < limitation) {
int index = student_sorted[currentStuIdx].index;
int value = student_sorted[currentStuIdx].value;
// if the current student is been chosen by another department
if (student[index].isChosenByDepartment == true) {
// ignore the current student
currentStuIdx++;
continue;
}
// if the value of current student == 0, end this process
if (value <= algorithmTool.lowBound) break;
// passed the abovementioned two examinations, join the student
// to the current department
student[index].isChosenByDepartment = true;
int numberTmp = addmitted_department[currentDepartment].number;
addmitted_department[currentDepartment].student_number[numberTmp] = student[index].student_number;
addmitted_department[currentDepartment].number++;
currentStuIdx++;
k++;
}
// if the department does not receive any students
if (addmitted_department[currentDepartment].number == 0) {
// join it to unlucky_department
unlucky_department[unlucky_department_number++] = department[currentDepartment].department_number;
}
}
// search for unlucky students
for (int i = 0; i < 300; i++) {
// if the student has not been chosen by any departments
if (student[i].isChosenByDepartment == false) {
unlucky_student[unlucky_student_number++] = student[i].student_number;
}
}
}