Question

Como implementar uma solução computacional para o problema do casamento (marriage-matching)?

Answer 1

Uma implementação bem ineficiente baseada em busca exaustiva é

import numpy as np
import matplotlib.pyplot as plt
from itertools import permutations           

np.random.seed(0)

def the_rank(preferenceMatrix,subject,passive):
    return np.where(preferenceMatrix[subject][:]==passive)[0][0]

def is_stable(menPreferences,womenPreferences,manDating,womanDating):
    n=np.shape(menPreferences)[0]    
    for man in range(n):        
        for woman in range(n):
            if((manDating[man]!=woman)and(the_rank(womenPreferences,woman,man)<the_rank(womenPreferences,woman,womanDating[woman]))and (the_rank(menPreferences,man,woman)<the_rank(menPreferences,man,manDating[man]))):
                return False
    return True    

def stable_marriage(menPreferences,womenPreferences):
    n=np.shape(menPreferences)[0]    

    thePermutations=list(permutations(range(0,n)))    
    numberPermutations=len(thePermutations)
    womanDating=np.zeros([n])

    for i in range(numberPermutations):
        print i
        manDating=np.array(thePermutations[i][:]) # For men
        womanDating[manDating]=range(n)
        if(is_stable(menPreferences,womenPreferences,manDating,womanDating)):
            print manDating

if __name__ == '__main__':
    # Men
    # Bob 0, Jim 1, Tom 2
    #Women 
    # Ann 0, Lea 1, Sue 2    
    n=3

    menPreferences=np.empty([n,n])
    menPreferences[0][:]=1,0,2
    menPreferences[1][:]=1,2,0
    menPreferences[2][:]=2,1,0    

    womenPreferences=np.empty([n,n])
    womenPreferences[0][:]=1,2,0
    womenPreferences[1][:]=2,0,1
    womenPreferences[2][:]=1,2,0        

    stable_marriage(menPreferences,womenPreferences)

Answer 2

A solução é clássica é dada por esse algoritmo introduzido por David Gale and Lloyd Shapley:

import numpy as np
import matplotlib.pyplot as plt
from itertools import permutations 
from collections import deque


np.random.seed(0)

def the_rank(preferenceMatrix,subject,passive):
    return np.where(preferenceMatrix[subject][:]==passive)[0][0]

def is_stable(menPreferences,womenPreferences,manDating,womanDating):
    n=np.shape(menPreferences)[0]    
    for man in range(n):        
        for woman in range(n):
            if((manDating[man]!=woman)and(the_rank(womenPreferences,woman,man)<the_rank(womenPreferences,woman,womanDating[woman]))and (the_rank(menPreferences,man,woman)<the_rank(menPreferences,man,manDating[man]))):
                return False
    return True    

def stable_marriage_brute_force(menPreferences,womenPreferences):
    n=np.shape(menPreferences)[0]    

    thePermutations=list(permutations(range(0,n)))    
    numberPermutations=len(thePermutations)
    womanDating=np.zeros([n])

    for i in range(numberPermutations):
        print i
        manDating=np.array(thePermutations[i][:]) # For men
        womanDating[manDating]=range(n)
        if(is_stable(menPreferences,womenPreferences,manDating,womanDating)):
            print manDating

def stable_marriage(menPreferences,womenPreferences):
    n=np.shape(menPreferences)[0]    
    singleMen=deque()
    # Every men are looking for women
    for i in range(n):
        singleMen.append(i)
    manDatingPosition=np.empty([n]) # It keeps the position of the last (or actual) partner
    manDating=np.empty([n])
    womanDating=np.empty([n])
    for i in range(n):
        manDating[i]=-1
        manDatingPosition[i]=-1 
        womanDating[i]=-1
    while(len(singleMen)!=0):
        man=singleMen.popleft()
        manDatingPosition[man]=manDatingPosition[man]+1
        manDating[man]=menPreferences[man][manDatingPosition[man]]
        theLuckWoman=manDating[man]
        if(womanDating[theLuckWoman]==-1):
            womanDating[theLuckWoman]=man
        elif(the_rank(womenPreferences,theLuckWoman,man)<the_rank(womenPreferences,theLuckWoman,womanDating[theLuckWoman])):
            singleMen.append(womanDating[theLuckWoman])
            womanDating[theLuckWoman]=man            
        else:            
            singleMen.append(man)                                    
    print manDating     


if __name__ == '__main__':
    # Men
    # Bob 0, Jim 1, Tom 2
    #Women 
    # Ann 0, Lea 1, Sue 2    
    n=3

    menPreferences=np.empty([n,n])
    menPreferences[0][:]=1,0,2
    menPreferences[1][:]=1,2,0
    menPreferences[2][:]=2,1,0    

    womenPreferences=np.empty([n,n])
    womenPreferences[0][:]=1,2,0
    womenPreferences[1][:]=2,0,1
    womenPreferences[2][:]=1,2,0        

    stable_marriage_brute_force(menPreferences,womenPreferences)
    stable_marriage(menPreferences,womenPreferences)