The Stable Marriage Problem

stable-marriage-problem.c

void stableMarriage(int prefer[ ][MAX], int rank[ ][MAX], int fiancee[ ], int n)‏
{
	int i, n, m, w, s, temp;
	int next[MAX];
	for (i = 1; i <= n; i++)	//  initialisation
	{
		next[i] = fiancee[i] = 0;  rank[i][0] = n + 1;
	}
	for (m = 1; m <= n; m++)‏
	{
		s = m;		//  next suitor
		while (s > 0)	//  repeats after broken engagement
		{
			next[s] = next[s] + 1;	
			w = prefer[s, next[s]];	 //  suitor’s next preference
			if (rank[w, s] < rank[w, fiancee[w]])	//  woman checks
			{		//  break engagement
				temp = fiancee[w];	//  woman w
				fiancee[w] = s;		//  prefers suitor s
				s = temp;			//  to fiancee who
			}						//  is new suitor
		}
	}
}

The algorithm is going to try to build stable pairings.

Each man, in turn, becomes a suitor and seeks a bride by choosing his highest
preference.

If she is already engaged to a man whom she prefers, then the suitor tries his next preference and continues until he finds a woman who is either not engaged or prefers the suitor to her present fiancée.

If the woman is not engaged then she and the suitor become engaged, and the next man in the list becomes the suitor.

If the woman is already engaged, but prefers the suitor, she breaks her engagement and becomes engaged to the suitor, and her ex-fiancée becomes the new suitor.

In each case, the new suitor tries his next preference.

Suitors keep trying until they find brides – breaking engagements along the way
where necessary!