Well, as a medical student, I don't have time for huge blog posts.
3 days until my last exam as a M2.
M3 is the start of clinical setting learning. Bed side learning.
Our group needs to decide who goes into which group, for certain blocks.
Each block offers different specialties.
Me, I want to get into a certain Surgery ward. Others specifically want to go
to a certain hospital, OB/GYN, etc..
Resident matching to hospital uses the Stable Matching algorithm,
probably adjusted to be polyandrous.
Those guys who made the algorithm got a Nobel Prize in Economics.
I think the resident match using their matching had a lot to do with it.
Well, me being a CS major, and seeing how that algorithm will greatly fit our problem,
I started searching.. for code. Yes I'm a script kiddy. There's a reason I switched my career :O.
Anyways, I found one.
at: http://cs.slu.edu/~goldwasser/courses/slu/csci314/2006_Spring/lectures/marriageAlgorithm/
I also hacked away at a Google Spreadsheet to create a random example of a rotation selection situation.
Turns out their script engine is really powerful, and you can use the Google Apps to create
Forms, and pull/push data into whatever you want! Maybe I'll port my code into Google Script someday.
Without further ado, here's my modified code. Amazing algorithm. Simple to understand, works like a charm :)
I know this won't be the only factor in setting a system for students to select who to go to where, but I think this'll greatly automate the sorting process, what our class reps probably would end up doing.
Update 30/03/2014: I've since done some modification to the code. All of it is now maintained in GitHub: https://github.com/lovebes
"""
An edited source code.
Demo of Gale-Shapley stable marriage algorithm.
Original Code at:
http://cs.slu.edu/~goldwasser/courses/slu/csci314/2006_Spring/lectures/marriageAlgorithm/
What is changed by Seungjin Kim:
Edited to be in polyandry mode, by Seungjin Kim
Also accounts for special to special sub group matching. Special husbands can ONLY go into special wives.
Usage is:
python matching.py [studentsChoice] [sitesRank] [sitesCapacity] [b7Sites] [specStudentList]
or
python marriage.py [studentsChoice] [sitesRank] [sitesCapacity] [b7Sites] [specStudentList] V
for verbose mode.
and likewise for the womenfile, where there should be precisely same
number of men as with women, and the identifiers should be
self-consistent between the two files.
"""
import sys
class Person:
"""
Represent a generic person
"""
def __init__(self,name,priorities):
"""
name is a string which uniquely identifies this person
priorities is a list of strings which specifies a ranking of all
potential partners, from best to worst
"""
self.name = name
self.priorities = priorities
self.partner = None
def __repr__(self):
return 'Name is ' + self.name + '\n' + \
'Partner is currently ' + str(self.partner) + '\n' + \
'priority list is ' + str(self.priorities)
class Man(Person):
"""
Represents a man
"""
def __init__(self,name,priorities,specialList):
"""
name is a string which uniquely identifies this person
priorities is a list of strings which specifies a ranking of all
potential partners, from best to worst
"""
Person.__init__(self,name,priorities)
# flag if name matches name in specialList
self.amSpecial = False
for name in specialList:
if self.name == name:
self.amSpecial = True
print self.name+' is special'
self.proposalIndex = 0 # next person in our list to whom we might propose
def nextProposal(self):
goal = self.priorities[self.proposalIndex]
self.proposalIndex += 1
return goal
def __repr__(self):
return Person.__repr__(self) + '\n' + \
'next proposal would be to ' + self.priorities[self.proposalIndex]
class Woman(Person):
"""
Represents a woman
"""
def __init__(self,name,priorities,husbandReq,specialList,specHubbyList):
"""
name is a string which uniquely identifies this person
priorities is a list of strings which specifies a ranking of all
potential partners, from best to worst
"""
Person.__init__(self,name,priorities)
# flag if name matches name in specialList
self.amSpecial = False
for name in specialList:
if self.name == name:
self.amSpecial = True
print self.name+' is special'
self.specHubbyArr = specHubbyList #maintain list of hubbies that you need to take!!
# now compute a reverse lookup for efficient candidate rating
self.ranking = {}
for rank in range(len(priorities)):
self.ranking[priorities[rank]] = rank
self.husbands = int(husbandReq) #will be populated by file
self.husbandsArr = [] #limit by self.husbands. Array of int that are index values of priorities array.
def evaluateProposal(self,suitor):
"""
Evaluates a proposal, though does not enact it.
suitor is the string identifier for the man who is proposing
returns True if proposal should be accepted, False otherwise
"""
# if hubby is special and wife is not special, just say no!!
if not self.amSpecial:
for hubby in self.specHubbyArr :
if suitor == hubby:
print self.name+" won't accept a special hubby "+suitor+" because wife not special"
return False
#have to find if suitor has a better ranking than any of the currently held husbands.
if len(self.husbandsArr) == self.husbands: #if husbandsArr full, see if suitor is a better match.
count = 0
for hubby in self.husbandsArr:#hubby is integer for priorities. Can use it to compare ranking. Lower # == better suitor
if self.ranking[suitor] < hubby:
count += 1
return count > 0
#if husbandsArr not full, just say yes.
return len(self.husbandsArr) < self.husbands
def husbandsFull(self):
return len(self.husbandsArr) == self.husbands
def addHubby(self,hubbyName):
self.husbandsArr.append(self.ranking[hubbyName])
self.husbandsArr.sort()
def popHubby(self):
#return name of popped hubby
return self.priorities[self.husbandsArr.pop()]
def parseFile(filename):
"""
Returns a list of (name,priority) pairs.
"""
people = []
f = file(filename)
for line in f:
pieces = line.split(':')
name = pieces[0].strip()
if name:
priorities = pieces[1].strip().split(',')
for i in range(len(priorities)):
priorities[i] = priorities[i].strip()
people.append((name,priorities))
f.close()
return people
def parseFile2(filename):
"""
Populates how many husbands one wife needs.
Returns a list of (wife,numHusband) pairs.
"""
wives = []
f = file(filename)
for line in f:
pieces = line.split(':')
name = pieces[0].strip()
if name:
husbands = pieces[1].strip()
wives.append((name,husbands))
f.close()
return wives
def parseFile3(filename):
#get the comma-delimited one line info of either special husbands and special wives
f = file(filename)
arr = f.readline().strip().split(',')
f.close()
return arr
def printPairings(men):
for man in men.values():
print man.name,'is paired with',str(man.partner)
def printPairings2(menArr):
newArr = []
for man in menArr:
#print man[1].name.ljust(10,' '),str(man[1].partner),'\tno '+str(man[1].proposalIndex)+' in preference'
newArr.append([man[1].name,str(man[1].partner),man[1].proposalIndex])
newArr.sort(key=lambda x: x[1])
for man in newArr:
print "Site: "+man[1].ljust(10,' ')+man[0].ljust(10,' ')+str(man[2])+" in preference"
def printPairings3(womenArr,men):
newArr = []
for woman in womenArr:
#print man[1].name.ljust(10,' '),str(man[1].partner),'\tno '+str(man[1].proposalIndex)+' in preference'
partArr = []
for hubby in woman[1].husbandsArr:
partArr.append([woman[1].name,woman[1].priorities[hubby],hubby, men[woman[1].priorities[hubby]].proposalIndex])
partArr.sort(key=lambda x: x[2])
newArr.append(partArr)
for woman in newArr:
for hubby in woman:
print "Site: "+hubby[0].ljust(10,' ')+hubby[1].ljust(10,' ')+str(hubby[2]+1).ljust(3,' ')+"in Site's preference, "+str(hubby[3])+" in Student's preference"
def dict2Arr(dictionary):
dictlist = []
for key, value in dictionary.iteritems():
temp = [key,value]
dictlist.append(temp)
return dictlist
if __name__=="__main__":
verbose = len(sys.argv)>6
# get a list of the special condition husbands that can only match to special wives. arg #5
specHubbyArr = parseFile3(sys.argv[5])
# get a list of special wives #4
specWivesArr = parseFile3(sys.argv[4])
# initialize dictionary of men
menlist = parseFile(sys.argv[1])
men = dict()
for person in menlist:
men[person[0]] = Man(person[0],person[1],specHubbyArr)
unwedMen = men.keys()
# initialize dictionary of women
womenlist = parseFile(sys.argv[2])
husbandReqs = parseFile2(sys.argv[3])
dictOne = dict(womenlist)
dictTwo = dict(husbandReqs)
combined = dict()
for name in set(dictOne.keys() + dictTwo.keys()):
combined[name] = [dictOne.get(name,0), dictTwo.get(name,0)]
combinedWomen = []
for name in combined:
combinedWomen.append([ name ] + combined[name])
women = dict()
for person in combinedWomen:
women[person[0]] = Woman(person[0],person[1],person[2],specWivesArr,specHubbyArr)
############################### the real algorithm ##################################
while unwedMen:
m = men[unwedMen[0]] # pick arbitrary unwed man
w = women[m.nextProposal()] # identify highest-rank woman to which
# m has not yet proposed
if verbose: print m.name,'proposes to',w.name
if w.evaluateProposal(m.name):#means also that hubbyArr is full, and if so, gotta pop to make space.
if verbose: print ' ',w.name,'accepts the proposal'
if w.husbandsFull():
# last hubby in hubbyArr is dumped, as that is least suitable
mOld = men[w.popHubby()]
mOld.partner = None
unwedMen.append(mOld.name)
# then add the new man
w.addHubby(m.name)
unwedMen.remove(m.name)
m.partner = w.name
else:
#if not full, and a nice suitor, just add him to the pack
unwedMen.remove(m.name)
w.addHubby(m.name)
m.partner = w.name
else:
if verbose: print ' ',w.name,'rejects the proposal'
if verbose:
print "Tentative Pairings are as follows:"
printPairings(men)
print
#####################################################################################
menArr = dict2Arr(men)
menArr.sort(key=lambda x: x[0])
womenArr = dict2Arr(women)
womenArr.sort(key=lambda x: x[0])
# we should be done
print "Final Pairings are as follows:"
printPairings2(menArr)
printPairings3(womenArr,men)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment