Este notebook tem como finalidade realizar a tradução e as interações de cada passo do problema do Stable Marriage Problem. O codigo original esta em Rosetta Code e esse codigo serve apenas para propositos educacionais.
In [1]:
import copy
# Preferencia dos homens
guyprefers = {
'abe': ['abi', 'eve', 'cath', 'ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay'],
'bob': ['cath', 'hope', 'abi', 'dee', 'eve', 'fay', 'bea', 'jan', 'ivy', 'gay'],
'col': ['hope', 'eve', 'abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan'],
'dan': ['ivy', 'fay', 'dee', 'gay', 'hope', 'eve', 'jan', 'bea', 'cath', 'abi'],
'ed': ['jan', 'dee', 'bea', 'cath', 'fay', 'eve', 'abi', 'ivy', 'hope', 'gay'],
'fred': ['bea', 'abi', 'dee', 'gay', 'eve', 'ivy', 'cath', 'jan', 'hope', 'fay'],
'gav': ['gay', 'eve', 'ivy', 'bea', 'cath', 'abi', 'dee', 'hope', 'jan', 'fay'],
'hal': ['abi', 'eve', 'hope', 'fay', 'ivy', 'cath', 'jan', 'bea', 'gay', 'dee'],
'ian': ['hope', 'cath', 'dee', 'gay', 'bea', 'abi', 'fay', 'ivy', 'jan', 'eve'],
'jon': ['abi', 'fay', 'jan', 'gay', 'eve', 'bea', 'dee', 'cath', 'ivy', 'hope']}
# Preferencia das mulheres
galprefers = {
'abi': ['bob', 'fred', 'jon', 'gav', 'ian', 'abe', 'dan', 'ed', 'col', 'hal'],
'bea': ['bob', 'abe', 'col', 'fred', 'gav', 'dan', 'ian', 'ed', 'jon', 'hal'],
'cath': ['fred', 'bob', 'ed', 'gav', 'hal', 'col', 'ian', 'abe', 'dan', 'jon'],
'dee': ['fred', 'jon', 'col', 'abe', 'ian', 'hal', 'gav', 'dan', 'bob', 'ed'],
'eve': ['jon', 'hal', 'fred', 'dan', 'abe', 'gav', 'col', 'ed', 'ian', 'bob'],
'fay': ['bob', 'abe', 'ed', 'ian', 'jon', 'dan', 'fred', 'gav', 'col', 'hal'],
'gay': ['jon', 'gav', 'hal', 'fred', 'bob', 'abe', 'col', 'ed', 'dan', 'ian'],
'hope': ['gav', 'jon', 'bob', 'abe', 'ian', 'dan', 'hal', 'ed', 'col', 'fred'],
'ivy': ['ian', 'col', 'hal', 'gav', 'fred', 'bob', 'abe', 'ed', 'jon', 'dan'],
'jan': ['ed', 'hal', 'gav', 'abe', 'bob', 'jon', 'col', 'ian', 'fred', 'dan']}
guys = sorted(guyprefers.keys())
gals = sorted(galprefers.keys())
In [2]:
guys
Out[2]:
In [3]:
gals
Out[3]:
In [4]:
def check(engaged):
inverseengaged = dict((v,k) for k,v in engaged.items())
for she, he in engaged.items():
shelikes = galprefers[she]
shelikesbetter = shelikes[:shelikes.index(he)]
helikes = guyprefers[he]
helikesbetter = helikes[:helikes.index(she)]
for guy in shelikesbetter:
guysgirl = inverseengaged[guy]
guylikes = guyprefers[guy]
if guylikes.index(guysgirl) > guylikes.index(she):
print(f'{she} e {guy} gostam mais de si mesmos do que os seus atuais parceiros: {he} e {guysgirl}, respectivamente')
return False
for gal in helikesbetter:
girlsguy = engaged[gal]
gallikes = galprefers[gal]
if gallikes.index(girlsguy) > gallikes.index(he):
print(f'{he} e {gal} gostam mais de si mesmos do que os seus atuais parceiros: {she} e {girlsguy}, respectivamente')
return False
return True
In [5]:
def matchmaker():
# Lista de caras disponiveis ()
guysfree = guys[:]
# Lista de noivados
engaged = {}
# Copia das listas de preferencias
guyprefers2 = copy.deepcopy(guyprefers)
galprefers2 = copy.deepcopy(galprefers)
# Enquanto houver homens disponiveis
while guysfree:
print(f'0. Caras livres: {guysfree}')
# Pega o primeiro homem da lista
guy = guysfree.pop(0)
print(f'1. Homem a fazer a proposta: {guy}')
# Pega a lista de preferencias desse homem
guyslist = guyprefers2[guy]
print(f'2. Preferencias de {guy}: {guyslist}')
# Pega a primeira preferencia do homem
gal = guyslist.pop(0)
print(f'3. Pega a primeira preferencia de {guy} que eh: {gal}')
# Busca na lista de propostas o status pra ver se a mulher esta noiva ou não
fiance = engaged.get(gal)
print(f'4. {gal} esta noiva? - Resposta: {fiance}')
if not fiance: # Se ela não estiver noiva
## Ela esta livre
print(f'5a. {gal} esta livre')
engaged[gal] = guy
print(f'5b. {guy} esta noivo de {gal} \n')
else:
# Se o homem fez a proposta para uma mulher que ja tem um noivo
# Pega as preferencias dessa mulher e coloca em uma lista.
print(f'6a. {gal} esta noiva de {fiance}')
print(f'6b. Pega a lista de preferencias de {gal}')
galslist = galprefers2[gal]
print(f'6c. As preferencias de {gal} são \n {galslist}')
print(f'6d. Posição do noivo atual {galslist[galslist.index(fiance)]}: {galslist.index(fiance)}')
print(f'6e. Posição da proposta atual {galslist[galslist.index(guy)]}: {galslist.index(guy)}')
if galslist.index(fiance) > galslist.index(guy):
# She prefers new guy
print(f'7a. {gal} prefere o novo cara {guy}')
engaged[gal] = guy
print(f'7b. {gal} largou {fiance} pra ficar com {guy}')
if guyprefers2[fiance]:
print(f'8a. Pega as preferencias do {fiance}')
print(f'8b. {fiance} pode tentar {guyprefers2[fiance]}')
print(f'8c. {fiance} vai para a lista de caras livres')
# Ex has more girls to try
guysfree.append(fiance)
print(f'8d. Caras livres {guysfree} \n')
else:
# She is faithful to old fiance
print(f'9. O atual de {gal} ({fiance}) eh melhor do que ({guy})')
if guyslist:
# Look again
print(f'10a. {guy} vai para a lista de caras livres')
guysfree.append(guy)
print(f'10b. Caras livres: {guysfree} \n')
return engaged
In [6]:
print('\nNoivados:')
engaged = matchmaker()
In [7]:
print('\nNoivados')
engaged
Out[7]:
In [8]:
print('\nCasais:')
print(' ' + ',\n '.join('%s esta noivo de %s' % couple
for couple in sorted(engaged.items())))
In [9]:
print('\nTeste de estabilidade dos noivados - PASSOU'
if check(engaged) else 'Teste de estabilidade dos noivados - FALHOU')
In [10]:
print('\nTrocando dois noivados para introduzir um erro')
engaged[gals[0]], engaged[gals[1]] = engaged[gals[1]], engaged[gals[0]]
for gal in gals[:2]:
print(f'{gal} esta noiva de {engaged[gal]}')
In [11]:
print('\nCasais:')
print(' ' + ',\n '.join('%s esta noivo de %s' % couple
for couple in sorted(engaged.items())))
In [12]:
print('\nTeste de estabilidade dos noivados - PASSOU'
if check(engaged) else 'Teste de estabilidade dos noivados - FALHOU')
In [ ]: