forked from YasinEhsan/CPPrograms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
stableMarriage.cpp
72 lines (65 loc) · 2.54 KB
/
stableMarriage.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
//YASIN EHSAN
//specs: http:https://venus.cs.qc.cuny.edu/~jchen/CS211/Projects/Marriage
#include<iostream>
using namespace std;
bool ok(int q[], int c) { // Finish this code
static int mp[3][3] = { { 0,2,1 }, // Man#0's preferences
{ 0,2,1 }, // Man#1's preferences
{ 1,2,0 } }; // Man#2's preferences
static int wp[3][3] = { { 2,1,0 }, // Woman#0's preferences
{ 0,1,2 }, // Woman#1's preferences
{ 2,0,1 } }; // Woman#2's preferences
/*Similar to 1D Queens, use a loop to check the array.
Inside the loop we chould check for 3 conditions
First condition checks is the same women is married to two different man *hint we need to check if two things are equal*
Second condition checks if (Man#i) and (Man#c's wife) both like each other more than their own spouse
Third condition checks if (Man#c) and (Man#i's wife) both like each other more than their own spouse
mp[i][j] tells you how much Man#i likes Woman#j. (0 = favorite; 2 = least favorite)
wp[i][j] tells you how much Woman#i likes Man#j.
mp[i][q[i]] tells you how much Man#i likes his own wife.
mp[i][q[c]] tells you how much Man#i likes Man#c's wife.
wp[q[i]][i] tells you how much Man#i's wife likes Man#i.
wp[q[i]][c] tells you how much Man#i's wife likes Man#c.
If mp[i][q[c]] < mp[i][q[i]], it means that Man#i likes Man#c's wife more than his own wife
*/
for(int i = 0; i < c; i++){
if(q[i] == q[c])
return false;//row test
if(mp[i][q[i]] > mp[i][q[c]] && wp[q[c]][c] > wp[q[c]][i] || mp[c][q[c]] > mp[c][q[i]] && wp[q[i]][i] > wp[q[i]][c])
return false;//edge case.
}
return true;
}
void print(int q[]) {
static int solution = 0;
cout << "Solution #" << ++solution << ":\n man\tWoman\n";
for(int i = 0; i < 3; i++)
cout << " " << i << "\t" << q[i] << endl; //diff from java
//in java you can concatenate with a "+". cpp needs "<<"
}
int main() {
//same backtrack as all prev projects. Pretty cool.
//***Def showing up on midterm!!!
int q[3] = {};
int c = 0;
while (c >= 0) {
c++;
if(c == 3){ //array ends at three.
print(q);
c--;
}
else
q[c] = -1;
while (c >= 0) {
q[c]++;
if(q[c] == 3)
c--;
else if(ok(q, c))
break;
}
}
return 0;
}
// This project was way easier than I thought.
// I can see how changing just one variable, array length, the same algorithm can be used over and over again. Really simplifies the code.
// Hardest part: grasping the second if condition