Sorry if I'm posting too much here but... Well, I'm kind of stubborn and I'm REALLY trying to learn this stuff FAST. (Although I do understand that learning something quickly doesn't exactly make you good at it, that comes with experience.)
So my program takes this Input file and does a bunch of manipulation (all of which is working JUST FINE, so we'll skip the explanation.) What we end up with is a list of Engineers, and who they want to be PAIRED with the most, ordered by preference. (There's a bunch of parsing needed to GENERATE that list, but I know my code is functioning 100% properly on all of that.)
Ultimately, what we're left with is this:
vector < vector<int> > engPrefs;
Which we need to parse into THIS:
vector<int> engPairs;
Here's what engPrefs looks like before we parse using the algorithm;
Engineer 0: 7 6 5 4
Engineer 1: 5 6 4 7
Engineer 2: 4 6 7 5
Engineer 3: 7 6 4 5
Engineer 4: 2 0 3 1
Engineer 5: 1 0 2 3
Engineer 6: 0 1 2 3
Engineer 7: 3 0 2 1
|
(The first line above is actually "cout << "Engineer " << i << ": " engPrefs[0][0] << " " << engPrefs[0][1]" etc - Keep in mind, we pair the first half of engineers with the second half.)
The way this is SUPPOSED to work (Gale-Shapley algorithm) is that you start with Engineer 0, check who he wants to be paired with most, and "pre-pair" them up. Then you move onto the next Engineer and do the same. However, in the case above, we'll come to Engineer 3, and we'll discover that 7 has already been pre-paired with 0. So then, we're supposed to find out who 7 would RATHER be paired with, 3 or 0, in this case it would be 3. So you pair 3 with 7 and UN-pair 0 and try 0's NEXT favorite. Rinse & Repeat until everyone is paired - At this point, the pairing is considered "Stable" and we commit it to "vector<int> engPairs;" for output. That's how it SHOULD work.
I can't even begin to fully understand how best to break this down into a functioning C++ program. Here's my current, total-failure of code, which implemented an entirely different (and incorrect) strategy - Enter my Fail-Shapley Algorithm:
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
|
for (int i = 0; i < startSetTwo; i++)
{
//We need to take the first engineer in <Insert Engineer Number
//Here>'s preference array and make sure no other engineer has
//the same first choice.
vector<int> matches;
int currentIteration = 0;
restart:
int toCheck = engPrefs[i][currentIteration];
matches.clear();
//Check to see if their favorite has been matched already...
vector<int>::iterator mat = find(engPairs.begin(), engPairs.end(), toCheck);
if (mat == engPairs.end() ) {
for (int j = i+1; j < startSetTwo; j++) //For all engineers in Set 1 after the one we're pairing.
{
//Check to see if the Engineer we're matching against has same preference
vector<int>::iterator it = find(engPrefs[j].begin(), engPrefs[j].end(), toCheck);
int position = int(it-engPrefs[j].begin());
if (position <= currentIteration) {
matches.push_back(j);
}
}
//If we found matches, we plug all the matched engineers into
//the matches vector and see which one comes first on
//Engineer B's list.
if (matches.size() > 0) {
matches.push_back(i);
//NOW we need to DO something about these matches - Check the toCheck Engineer's preferences
//to see who they want to be with among the matched Engineers.
vector<int> matchPositions;
vector<int>::iterator it = find_first_of(engPrefs[toCheck].begin(), engPrefs[toCheck].end(), matches.begin(), matches.end());
int tempPosition = int(it-engPrefs[toCheck].begin());
int tempMatch = engPrefs[toCheck][tempPosition];
//If they want to be with eng[i] the MOST, pair them up - Otherwise, we're going to restart the process.
if (tempMatch = i) {
engPairs.push_back(engPrefs[i][currentIteration]);
} else {
//Restart the process.
currentIteration++;
goto restart; //Yeah, I know...
}
}
//If we find no matches, all is good, and we pair the two little
//fellas together.
else {
engPairs.push_back(engPrefs[i][currentIteration]);
}
}
//If the toCheck Engineer is already paired, skip and try next in set.
else if (mat != engPairs.end()) {
currentIteration++;
goto restart; //Yeah, I know...
}
}
|
This code is bug-ridden and throwing me segmentation faults, but it's only slightly modified from my last version which was ALMOST correct, but was still pairing (using the example above) 0 to 7 and 3 to 6 which was incorrect.
I know this was long and lame, and I apologize, but you can see what I'm working with already. I'm not asking for anyone to FIX this code for me, I'm asking for a point in the right direction - Where do I go from here?
Again, many thanks in advance.