Gale-Shapley algorithm for stable matching problem

Gale-Shapley (G-S) algorithm is to solve stable matching (or stable marriage) problem.

Stable matching is a story about two groups, men and women.

Each man like more than one woman but does not like identically.

Also, each woman likes more than one man but does not like identically.

If you want to contact each other in the their satisfaction, you will be able to G-S algorithm.

Proposor (like men); Acceptor (like women)
Cited from Wikipedia

G-S algorithm is really simple.

// Cited from Wikipedia, http://en.wikipedia.org/wiki/Stable_marriage_problem

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked such woman to whom he has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}