Skip to content
A pure javascript implementation of the Stable Matching Algorithm.
JavaScript
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.
.gitignore
LICENSE.txt
Makefile
README.md
package.json
stablematch.js
test-stablematch.spec.js

README.md

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.

Something went wrong with that request. Please try again.