A generic implementation of the Stable Match class of algorithms.
- See:
examples/example_1.rb
- See:
test/functional/nrmp_test.rb
- See:
test/functional/stable_marriage_test.rb
- Run:
rake example
The idea behind stable matching is the following: You have two sets of data that you would like to find the most ideal matching between. Stable matching means that candidates from either set might remain unmatched. Unstable matching means that matches are forced even if they are not ideal.
Your inputs are two hashes where the keys are known as 'target's to StableMatch. Targets ideally are domain specific objects to your application. The value in the hash for each target is an array of preferences for the target. (See the note below about when preferences are themselves each an Array object.)
Preferences are an ordered array of 'target's belonging to the other set such that, the lower the index, the higher the preference. This is required and checked at runtime. It can be an empty array, but all preferences must belong to the other set.
The final argument that a Candidate
object can be instantiated with is
called match_positions
and equates to the number of matches that the
given target can acquire. This is optional and defaults to 1.
Let's talk about a dog-walker example. We have two domain classes: Dog and Walker. Let's say that the preferences will be determined by the weight and geographic location of the dog.
TODO !!
FIXME !!
this needs finished
- To match against objects that are arrays, they'll need to be
preemptively wrapped in another array when passing them a runner. See
the NRMP test in
test/functional
for example.
Install it yourself:
$ gem install stable_match
Add this line to your application's Gemfile:
gem 'stable_match'
And then execute:
$ bundle
- http://halfamind.aghion.com/the-national-resident-matching-programs-nrmp
- http://rosettacode.org/wiki/Stable_marriage_problem#Ruby
- http://en.wikipedia.org/wiki/Stable_marriage_problem#Algorithm
- http://en.wikipedia.org/wiki/National_Resident_Matching_Program
- http://www.nrmp.org/res_match/about_res/algorithms.html
- Fork it
- Create your feature branch (
git checkout -b my-new-feature
) - Commit your changes (
git commit -am 'Added some feature'
) - Push to the branch (
git push origin my-new-feature
) - Create new Pull Request