Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Gale-Shapley algorithm
# -*- coding: utf-8 -*-
import numpy as np
class Person():
def __init__(self, n):
self.preference = np.random.permutation(range(n))
self.preferred_queue = []
self.position = None
self.matching = False
def vote(self):
if self.position == None:
self.position = 0
return self.preference[self.position]
elif self.position < len(self.preference):
self.position += 1
return self.preference[self.position]
else:
return None
def pick(self):
for i, p in enumerate(self.preference):
if p in self.preferred_queue:
self.preferred_queue = []
if self.position == i:
return None, None
else:
p_old = self.position
self.position = i
return p, p_old
return None, None
def step(voters, pickers):
# blocking person votes
for i, voter in enumerate(voters):
if voter.matching == False:
voted = voter.vote()
if voted is not None:
women[voted].preferred_queue.append(i)
# all pickers pick
for i, picker in enumerate(pickers):
new_selected, old_selected = picker.pick()
if new_selected is not None:
voters[new_selected].matching = True
if old_selected is not None:
voters[old_selected].matching = False
return sum([voter.matching for voter in voters])
if __name__ == '__main__':
# setup
n = 10
men = [Person(n) for i in range(n)]
women = [Person(n) for i in range(n)]
i, matched = 0, 0
# matching process
while matched != n:
matched = step(men, women)
print ("Trial {}: {}/{} pairs are matching.".format(i, matched, n))
i += 1
print("\nResult: Matching, Order, Voter,s preference")
for m in men:
print m.matching, m.position, m.preference
Trial 0: 6/10 pairs are matching.
Trial 1: 7/10 pairs are matching.
Trial 2: 7/10 pairs are matching.
Trial 3: 9/10 pairs are matching.
Trial 4: 9/10 pairs are matching.
Trial 5: 9/10 pairs are matching.
Trial 6: 10/10 pairs are matching.
Result: Matching, Order, Voter,s preference
True 2 [8 6 0 3 9 4 2 1 5 7]
True 0 [9 0 6 5 3 7 4 1 2 8]
True 0 [0 3 8 7 1 6 2 9 5 4]
True 0 [8 5 9 2 3 7 6 0 4 1]
True 3 [9 3 2 7 1 6 8 4 0 5]
True 3 [2 3 1 7 8 4 6 9 5 0]
True 1 [2 6 9 7 1 3 8 0 4 5]
True 1 [6 4 2 9 8 0 7 1 3 5]
True 3 [3 2 1 9 4 7 0 8 6 5]
True 0 [2 5 0 3 4 6 9 1 7 8]
(Pdb)
Trial 0: 7/10 pairs are matching.
Trial 1: 7/10 pairs are matching.
Trial 2: 9/10 pairs are matching.
Trial 3: 9/10 pairs are matching.
Trial 4: 9/10 pairs are matching.
Trial 5: 9/10 pairs are matching.
Trial 6: 9/10 pairs are matching.
Trial 7: 9/10 pairs are matching.
Trial 8: 9/10 pairs are matching.
Trial 9: 9/10 pairs are matching.
Trial 10: 9/10 pairs are matching.
Trial 11: 9/10 pairs are matching.
Trial 12: 10/10 pairs are matching.
Result: Matching, Order, Voter,s preference
True 2 [3 2 9 4 0 7 1 8 5 6]
True 3 [7 2 9 8 5 4 0 6 3 1]
True 4 [0 2 5 9 3 1 8 4 7 6]
True 1 [8 5 1 9 0 7 2 4 3 6]
True 1 [0 2 1 8 5 7 9 3 4 6]
True 0 [6 8 0 4 2 1 7 5 9 3]
True 0 [1 8 3 6 2 9 4 7 5 0]
True 2 [8 2 1 5 0 7 3 9 4 6]
True 1 [2 6 0 5 9 4 3 1 8 7]
True 2 [7 9 4 6 5 0 2 1 3 8]
(Pdb)
Trial 0: 4/10 pairs are matching.
Trial 1: 8/10 pairs are matching.
Trial 2: 9/10 pairs are matching.
Trial 3: 9/10 pairs are matching.
Trial 4: 9/10 pairs are matching.
Trial 5: 9/10 pairs are matching.
Trial 6: 9/10 pairs are matching.
Trial 7: 9/10 pairs are matching.
Trial 8: 9/10 pairs are matching.
Trial 9: 9/10 pairs are matching.
Trial 10: 9/10 pairs are matching.
Trial 11: 9/10 pairs are matching.
Trial 12: 9/10 pairs are matching.
Trial 13: 9/10 pairs are matching.
Trial 14: 9/10 pairs are matching.
Trial 15: 9/10 pairs are matching.
Trial 16: 9/10 pairs are matching.
Trial 17: 9/10 pairs are matching.
Trial 18: 9/10 pairs are matching.
Trial 19: 9/10 pairs are matching.
Trial 20: 9/10 pairs are matching.
Trial 21: 9/10 pairs are matching.
Trial 22: 10/10 pairs are matching.
Result: Matching, Order, Voter,s preference
True 4 [7 4 6 0 5 3 8 2 1 9]
True 3 [0 3 6 4 7 9 1 5 2 8]
True 3 [7 2 4 9 5 6 8 3 1 0]
True 3 [3 1 6 9 4 0 7 2 5 8]
True 2 [0 2 8 6 4 7 9 3 1 5]
True 2 [0 4 9 6 1 5 7 3 8 2]
True 4 [0 3 7 4 1 6 2 8 9 5]
True 0 [1 2 6 4 3 8 0 7 5 9]
True 3 [7 9 1 3 8 4 6 0 5 2]
True 4 [3 6 8 7 2 9 5 1 4 0]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment