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)