Gale-Shipley Algorithm

gale.js

var men = {
    'Joe': ['Mary','Jane','Dorothy','Susan'],
    'Tim': ['Jane','Dorothy','Mary','Susan'],
    'Jack': ['Dorothy','Jane','Susan','Mary'],
    'Matt': ['Mary','Jane','Susan','Dorothy']
};

var women = {
    'Mary': ['Tim','Joe','Jack','Matt'],
    'Jane': ['Matt','Jack','Joe','Tim'],
    'Dorothy': ['Matt','Tim','Joe','Jack'],
    'Susan': ['Joe','Tim','Jack','Matt']
};

// Find an equilibrium in marriages
function stableMatching(menPref,womenPref) {
    this.engaged = {};
    this.proposals = {};
    this.manRank = {};
    
    // Setup proposal array and rankings
    for(var man in menPref) this.proposals[man] = {};
    for(var woman in womenPref) {
        var rank = 0;
        this.manRank[woman] = {};
        for(var man in womenPref[woman])
            this.manRank[woman][womenPref[woman][man]] = rank++;
    }

    // Return the next free man
    function freeMan() {
        for(var man in menPref) {
            if(engaged[man] === undefined) {
                for(var woman in womenPref) {
                    if(proposals[man][woman] === undefined) return [man,woman];
                }
            }
        }
        return null;
    };
    
    while(pair = freeMan()) {
        var man = pair[0];
        var woman = pair[1];
        proposals[man][woman] = true;
        if(engaged[woman] === undefined) {
            engaged[man] = woman;
            engaged[woman] = man;
        } else if(this.manRank[woman][man] < this.manRank[woman][engaged[woman]]) {
            delete engaged[engaged[woman]];
            engaged[man] = woman;
            engaged[woman] = man;
        }
    }
    
    return engaged;
}
var marriages = stableMatching(men,women);