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

+2 votos
219 visitas

## 2 Respostas

+1 voto
respondida Abr 9, 2016 por (5,501 pontos)

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)
0 votos
respondida Abr 29, 2016 por (5,501 pontos)

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)