Gale-Shapley algorithm

gs_algorithm.py

# -*- 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
    

result

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]