Nearsighted Paramecium Multiverse
    Share your code. npm Orgs help your team discover, share, and reuse code. Create a free org »

    stablematchpublic

    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.

    Keywords

    none

    install

    npm i stablematch

    Downloadsweekly downloads

    9

    version

    0.0.4

    license

    none

    repository

    github.com

    last publish

    collaborators

    • avatar