Instantly share code, notes, and snippets.

# smrmkt/gs_algorithm.py Last active Jun 15, 2016

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]