Stable Marriage

Template for homework
Note: The stable matching problem is very well known with a very well known solution, called the Gale-Shapley Algorithm (link shows importance of stable matching).
Video how explaining how it works. The solution presented in lecture is backtracking, not Gale-Shapley, which you will cover in CS323 (algorithms).

The Problem

Suppose we have n men and n woman, each with their own preference for the opposite sex.
Can we create a matching such that there is no unstable pairings?

What is an unstable pairing?:

An unstable pairing is one where a man likes another woman more than his current partner and that same woman likes that same man more than her current partner (In which case they would run away together--hence the unstable pairing).

The Algorithm

1. Start with a default array (an array set to all zero in this case).
2. Begin pairing up the first man and first available woman (a pair in this case is used by the matching array, the index represents the man, the value at that index represent the woman).
3. If we have backtracked beyond the first pairing, terminate.
4. If we match all people
1. print the matching
2. backtrack
3. Go back to 3.
5. Next, pair the next man and the next available woman.
6. Check to see if there is an unstable matching.
1. If there is not
Go back to 3.
2. there is a unstable matching
Pair the man with the next available woman. If there are no more available woman, backtrack (in this case backtracking means breaking up the current couple, and matching the man with the next available woman). Go back to 3.

The correct output is displayed below.