stablematch v0.0.4
stablematch
A pure javascript implementation of a Stable Matching Algorithm, which is used to provide a solution to the stable marriage problem (http://wikipedia.org/wiki/Stable_marriage_problem) using a left-optimized algorithm.
The core implementation was shamelessly scrubbed and adapted from the "toy" implementation by Paul Butler (https://github.com/paulgb/Python-Gale-Shapley/), adapted to javascript and improved to support asymmetric data sets.
Installation
This is the easy part, provided you have npm
installed:
npm install stablematch
Usage
Here is an example of how to pair up two six-element sets. Note the
use of amdefine, which allows
stablematch
to be used in any javascript-enabled context.
if ( typeof(define) !== 'function' )
var define = require('amdefine')(module);
define('stablematch', function(sma) {
// setup two sets that will be paired var setA = '1','2','3','4','5','6'; var setB = 'a','b','c','d','e','f';
// callback function rankA
returns the preference order
// of setB
given any element in setA
.
var rankA = function(a) {
switch ( a )
{
case '1': return 'a', 'd', 'b', 'f', 'e', 'c';
case '2': return 'c', 'a', 'b', 'd', 'e', 'f';
case '3': return 'a', 'b', 'd', 'c', 'e', 'f';
case '4': return 'd', 'a', 'b', 'e', 'c', 'f';
case '5': return 'a', 'b', 'c', 'f', 'd', 'e';
case '6': return 'b', 'a', 'd', 'c', 'e', 'f';
default: throw 'no such element "' + a + '" in set A';
}
};
// callback function rankB
returns the preference order
// of setA
given any element in setB
.
var rankB = function(b) {
switch ( b )
{
case 'a': return '1', '2', '3', '4', '5', '6';
case 'b': return '2', '1', '4', '3', '5', '6';
case 'c': return '5', '1', '6', '3', '2', '4';
case 'd': return '1', '3', '2', '5', '4', '6';
case 'e': return '4', '1', '3', '6', '2', '5';
case 'f': return '2', '1', '4', '3', '6', '5';
default: throw 'no such element "' + b + '" in set B';
}
};
// call stablematch.match() to pair all of the elements. var solution = sma.match(setA, setB, rankA, rankB);
// solution ::= // [ // '1', 'a', '2', 'b', '3', 'd', // '4', 'e', '5', 'c', '6', 'f' // ]
});
Performance and Optimality
The implementation is not intended to be the world's best... it was, after all, a quick-n-dirty implementation done one Saturday morning just so that a basic pairing could be done inside the syncml-js package...
If you care to improve it in any way, please do so! I'll accept any pull requests that don't break it and improve performance.