STABLE MARIAGE PROBLEM

stable_mariage_problem.rb

# <STABLE MARIAGE PROBLEM>
#
# Copyright (C) 2012 Shinnosuke TAKEDA All rights reserved.
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
# http://www.gnu.org/licenses/gpl.txt
require 'pp'

def make_matches(girls, boys)
  rank = []

  boys.each.with_index do |boy,boy_i|
    boy.each do |candidate|
      if rank.select{ |match| match[:girl] == candidate }.empty?
        rank << { :boy => boy_i, :girl => candidate }
        break
      else
        if girls[candidate].index(boy_i) >  girls[candidate].index(rank.select{ |match| match[:girl] == candidate }.first.fetch(:boy))
          rank.select{ |match| match[:girl] == candidate }.first.update({:boy => boy_i})
          break
        end
      end
    end
  end

  return rank

end

g = [[1, 2, 0],
     [1, 0, 2],
     [2, 1, 0]],

b = [[0, 2, 1],
     [1, 2, 0],
     [2, 0, 1]]

pp make_matches(g,b)