My Fail-Shapley Algorithm

[kresentphresh]

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:

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.

[ne555]

If I understand correctly

is that you start with Engineer 0, check who he wants to be paired with most, and "pre-pair" them up

I love you, you are mine

//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) { //you love me like I love you
	matches.push_back(j);
}

We well be together if you love as much as I love you (or more)

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];

Check if the iterator is valid

goto restart; //Yeah, I know... So?

[quirkyusername]

get rid of that goto and replace it with a do while loop, gotos aren't very c++