jweinst1
9/19/2015 - 8:20 AM

## stable marriage algorithm in ruby

stable marriage algorithm in ruby

``````#Stable Marriage algorithm

class Pairing
def initialize(name, choices)
@name = name
@choices = choices
@match = nil
end
def name
return @name
end
def choices
return @choices
end
def first_choice
return @choices[0]
end
def remove_first
@choices.delete_at(0)
end
def match
return @match
end
def set_match(elem)
@match = elem.name
end
end

def hash_to_pairings(elem)
paired_list = []
for thing in elem.keys
paired_list << Pairing.new(thing, elem[thing])
end
return paired_list
end

def is_match(pair1, pair2)
if pair1.first_choice == pair2.name
if pair2.first_choice == pair1.name
return true
else
return false
end
else
return false
end
end

def get_first_choices(accept, list)
matched = []
for elem in list
if elem.first_choice == accept.name
matched << elem
end
end
return matched
end

def check_rank(acceptor, chooser)
rank = 0
until rank == acceptor.choices.length do
if acceptor.choices[rank] == chooser.name
return rank+1
else
rank += 1
end
end
return rank+1
end

def find_best_match(acceptor, choosers)
choosers = get_first_choices(acceptor, choosers)
current = choosers[0]
count = 1
until count == acceptor.choices.length do
if check_rank(acceptor, current) < check_rank(acceptor, choosers[count])
current = choosers[count]
count += 1
else
count += 1
end
end
acceptor.set_match(current)
current.set_match(acceptor)
for elem in choosers
if elem.match == nil
elem.remove_first
end
end
end

def remove_matched(list)
for elem in list
if elem.match != nil
list.delete(elem)
end
end
return list
end

def is_all_matched(list)
for elem in list
if elem.match == nil
return false
end
end
return true
end

def match_items(acceptors, choosers)
accepted = hash_to_pairings(acceptors)
chosen = hash_to_pairings(choosers)
count = 0
until count == accepted.length do
find_best_match(accepted[count], chosen)
count += 1
end
return accepted
end``````