Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Deferred Acceptance Algorithm
from collections import defaultdict
def male_without_match(matches, males):
for male in males:
if male not in matches:
return male
def deferred_acceptance(male_prefs, female_prefs):
female_queue = defaultdict(int)
males = list(male_prefs.keys())
matches = {}
while True:
male = male_without_match(matches, males)
if not male:
break
female_index = female_queue[male]
female_queue[male] += 1
try:
female = male_prefs[male][female_index]
except IndexError:
matches[male] = male
continue
print('Trying %s with %s... ' % (male, female), end='')
prev_male = matches.get(female, None)
if not prev_male:
matches[male] = female
matches[female] = male
print('auto')
elif female_prefs[female].index(male) < \
female_prefs[female].index(prev_male):
matches[male] = female
matches[female] = male
del matches[prev_male]
print('matched')
else:
print('rejected')
return {male: matches[male] for male in male_prefs.keys()}
def test_popularity_contest():
"""Every male has the same preferences as every other male; same for females."""
FEMALES = ['F1', 'F2', 'F3']
MALES = ['M1', 'M2', 'M3', 'M4', 'M5']
MALE_PREFS = {key: FEMALES.copy() for key in MALES}
FEMALE_PREFS = {key: MALES.copy() for key in FEMALES}
matches = deferred_acceptance(MALE_PREFS, FEMALE_PREFS)
assert matches == {'M1': 'F1', 'M2': 'F2', 'M3': 'F3', 'M4': 'M4', 'M5': 'M5'}
def test_cycle():
"""Males have different preferences, while females have identical preferences."""
MALE_PREFS = {
'M1': ['F2'],
'M2': ['F1'],
}
FEMALE_PREFS = {
'F1': ['M1'],
'F2': ['M2'],
}
matches = deferred_acceptance(MALE_PREFS, FEMALE_PREFS)
assert matches == {'M1': 'F2', 'M2': 'F1'}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment