Package Exports

stablematch

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (stablematch) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

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.