Gale Shapley Source Code
If the title doesn’t ring any bells than stop reading now. Basically, I needed to implement the gale shapely algorithm for a uni assessment but whilst looking around for an implementation I could only find one in python here . The pseudo code for the algorithm from the wiki found here is this:
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 who he has not proposed to yet
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
}
}
Here is the algorithm implemented in AS3, there is a difference in the else if part where the “else some pair already exists” from the pseudo code is assumed in the AS3. Also, the last else from the pseudo code is missing since it is redundant.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public function galeShapely():void
{
var tempMan:Person = null;
var tempWoman:Person = null;
while(manArray.length > 0)
{
tempMan = manArray[0];
tempWoman = womanArray[tempMan.getNextPreferance() - 1];
if (tempWoman.getMatchedTo() == null)
{
tempWoman.setMatchedTo(manArray.shift());
}
else if (tempWoman.isBetterPreferance(tempMan.getIndex()))
{
manArray.push(tempWoman.getMatchedTo());
tempWoman.setMatchedTo(manArray.shift());
}
}
} |
Download the full source here
Pingback: Is there a fast, open-source implementation of the Gale-Shapley algorithm? - Quora
at line 6, do you mean:
while(manArray.length > 0)
December 14, 2011 at 3:07 am
Wow, must have happen when I was trying to get the syntax highlighting to work, fixed now. Thanks for pointing it out.
December 14, 2011 at 8:04 pm