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]:
['abe', 'bob', 'col', 'dan', 'ed', 'fred', 'gav', 'hal', 'ian', 'jon']

In [3]:
gals


Out[3]:
['abi', 'bea', 'cath', 'dee', 'eve', 'fay', 'gay', 'hope', 'ivy', 'jan']

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()


Noivados:
0. Caras livres: ['abe', 'bob', 'col', 'dan', 'ed', 'fred', 'gav', 'hal', 'ian', 'jon']
1. Homem a fazer a proposta: abe
2. Preferencias de abe: ['abi', 'eve', 'cath', 'ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay']
3. Pega a primeira preferencia de abe que eh: abi
4. abi esta noiva? - Resposta: None
5a. abi esta livre
5b. abe esta noivo de abi 

0. Caras livres: ['bob', 'col', 'dan', 'ed', 'fred', 'gav', 'hal', 'ian', 'jon']
1. Homem a fazer a proposta: bob
2. Preferencias de bob: ['cath', 'hope', 'abi', 'dee', 'eve', 'fay', 'bea', 'jan', 'ivy', 'gay']
3. Pega a primeira preferencia de bob que eh: cath
4. cath esta noiva? - Resposta: None
5a. cath esta livre
5b. bob esta noivo de cath 

0. Caras livres: ['col', 'dan', 'ed', 'fred', 'gav', 'hal', 'ian', 'jon']
1. Homem a fazer a proposta: col
2. Preferencias de col: ['hope', 'eve', 'abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan']
3. Pega a primeira preferencia de col que eh: hope
4. hope esta noiva? - Resposta: None
5a. hope esta livre
5b. col esta noivo de hope 

0. Caras livres: ['dan', 'ed', 'fred', 'gav', 'hal', 'ian', 'jon']
1. Homem a fazer a proposta: dan
2. Preferencias de dan: ['ivy', 'fay', 'dee', 'gay', 'hope', 'eve', 'jan', 'bea', 'cath', 'abi']
3. Pega a primeira preferencia de dan que eh: ivy
4. ivy esta noiva? - Resposta: None
5a. ivy esta livre
5b. dan esta noivo de ivy 

0. Caras livres: ['ed', 'fred', 'gav', 'hal', 'ian', 'jon']
1. Homem a fazer a proposta: ed
2. Preferencias de ed: ['jan', 'dee', 'bea', 'cath', 'fay', 'eve', 'abi', 'ivy', 'hope', 'gay']
3. Pega a primeira preferencia de ed que eh: jan
4. jan esta noiva? - Resposta: None
5a. jan esta livre
5b. ed esta noivo de jan 

0. Caras livres: ['fred', 'gav', 'hal', 'ian', 'jon']
1. Homem a fazer a proposta: fred
2. Preferencias de fred: ['bea', 'abi', 'dee', 'gay', 'eve', 'ivy', 'cath', 'jan', 'hope', 'fay']
3. Pega a primeira preferencia de fred que eh: bea
4. bea esta noiva? - Resposta: None
5a. bea esta livre
5b. fred esta noivo de bea 

0. Caras livres: ['gav', 'hal', 'ian', 'jon']
1. Homem a fazer a proposta: gav
2. Preferencias de gav: ['gay', 'eve', 'ivy', 'bea', 'cath', 'abi', 'dee', 'hope', 'jan', 'fay']
3. Pega a primeira preferencia de gav que eh: gay
4. gay esta noiva? - Resposta: None
5a. gay esta livre
5b. gav esta noivo de gay 

0. Caras livres: ['hal', 'ian', 'jon']
1. Homem a fazer a proposta: hal
2. Preferencias de hal: ['abi', 'eve', 'hope', 'fay', 'ivy', 'cath', 'jan', 'bea', 'gay', 'dee']
3. Pega a primeira preferencia de hal que eh: abi
4. abi esta noiva? - Resposta: abe
6a. abi esta noiva de abe
6b. Pega a lista de preferencias de abi
6c. As preferencias de abi são 
 ['bob', 'fred', 'jon', 'gav', 'ian', 'abe', 'dan', 'ed', 'col', 'hal']
6d. Posição do noivo atual abe: 5
6e. Posição da proposta atual hal: 9
9. O atual de abi (abe) eh melhor do que (hal)
10a. hal vai para a lista de caras livres
10b. Caras livres: ['ian', 'jon', 'hal'] 

0. Caras livres: ['ian', 'jon', 'hal']
1. Homem a fazer a proposta: ian
2. Preferencias de ian: ['hope', 'cath', 'dee', 'gay', 'bea', 'abi', 'fay', 'ivy', 'jan', 'eve']
3. Pega a primeira preferencia de ian que eh: hope
4. hope esta noiva? - Resposta: col
6a. hope esta noiva de col
6b. Pega a lista de preferencias de hope
6c. As preferencias de hope são 
 ['gav', 'jon', 'bob', 'abe', 'ian', 'dan', 'hal', 'ed', 'col', 'fred']
6d. Posição do noivo atual col: 8
6e. Posição da proposta atual ian: 4
7a. hope prefere o novo cara ian
7b. hope largou col pra ficar com ian
8a. Pega as preferencias do col
8b. col pode tentar ['eve', 'abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan']
8c. col vai para a lista de caras livres
8d. Caras livres ['jon', 'hal', 'col'] 

0. Caras livres: ['jon', 'hal', 'col']
1. Homem a fazer a proposta: jon
2. Preferencias de jon: ['abi', 'fay', 'jan', 'gay', 'eve', 'bea', 'dee', 'cath', 'ivy', 'hope']
3. Pega a primeira preferencia de jon que eh: abi
4. abi esta noiva? - Resposta: abe
6a. abi esta noiva de abe
6b. Pega a lista de preferencias de abi
6c. As preferencias de abi são 
 ['bob', 'fred', 'jon', 'gav', 'ian', 'abe', 'dan', 'ed', 'col', 'hal']
6d. Posição do noivo atual abe: 5
6e. Posição da proposta atual jon: 2
7a. abi prefere o novo cara jon
7b. abi largou abe pra ficar com jon
8a. Pega as preferencias do abe
8b. abe pode tentar ['eve', 'cath', 'ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay']
8c. abe vai para a lista de caras livres
8d. Caras livres ['hal', 'col', 'abe'] 

0. Caras livres: ['hal', 'col', 'abe']
1. Homem a fazer a proposta: hal
2. Preferencias de hal: ['eve', 'hope', 'fay', 'ivy', 'cath', 'jan', 'bea', 'gay', 'dee']
3. Pega a primeira preferencia de hal que eh: eve
4. eve esta noiva? - Resposta: None
5a. eve esta livre
5b. hal esta noivo de eve 

0. Caras livres: ['col', 'abe']
1. Homem a fazer a proposta: col
2. Preferencias de col: ['eve', 'abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan']
3. Pega a primeira preferencia de col que eh: eve
4. eve esta noiva? - Resposta: hal
6a. eve esta noiva de hal
6b. Pega a lista de preferencias de eve
6c. As preferencias de eve são 
 ['jon', 'hal', 'fred', 'dan', 'abe', 'gav', 'col', 'ed', 'ian', 'bob']
6d. Posição do noivo atual hal: 1
6e. Posição da proposta atual col: 6
9. O atual de eve (hal) eh melhor do que (col)
10a. col vai para a lista de caras livres
10b. Caras livres: ['abe', 'col'] 

0. Caras livres: ['abe', 'col']
1. Homem a fazer a proposta: abe
2. Preferencias de abe: ['eve', 'cath', 'ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay']
3. Pega a primeira preferencia de abe que eh: eve
4. eve esta noiva? - Resposta: hal
6a. eve esta noiva de hal
6b. Pega a lista de preferencias de eve
6c. As preferencias de eve são 
 ['jon', 'hal', 'fred', 'dan', 'abe', 'gav', 'col', 'ed', 'ian', 'bob']
6d. Posição do noivo atual hal: 1
6e. Posição da proposta atual abe: 4
9. O atual de eve (hal) eh melhor do que (abe)
10a. abe vai para a lista de caras livres
10b. Caras livres: ['col', 'abe'] 

0. Caras livres: ['col', 'abe']
1. Homem a fazer a proposta: col
2. Preferencias de col: ['abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan']
3. Pega a primeira preferencia de col que eh: abi
4. abi esta noiva? - Resposta: jon
6a. abi esta noiva de jon
6b. Pega a lista de preferencias de abi
6c. As preferencias de abi são 
 ['bob', 'fred', 'jon', 'gav', 'ian', 'abe', 'dan', 'ed', 'col', 'hal']
6d. Posição do noivo atual jon: 2
6e. Posição da proposta atual col: 8
9. O atual de abi (jon) eh melhor do que (col)
10a. col vai para a lista de caras livres
10b. Caras livres: ['abe', 'col'] 

0. Caras livres: ['abe', 'col']
1. Homem a fazer a proposta: abe
2. Preferencias de abe: ['cath', 'ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay']
3. Pega a primeira preferencia de abe que eh: cath
4. cath esta noiva? - Resposta: bob
6a. cath esta noiva de bob
6b. Pega a lista de preferencias de cath
6c. As preferencias de cath são 
 ['fred', 'bob', 'ed', 'gav', 'hal', 'col', 'ian', 'abe', 'dan', 'jon']
6d. Posição do noivo atual bob: 1
6e. Posição da proposta atual abe: 7
9. O atual de cath (bob) eh melhor do que (abe)
10a. abe vai para a lista de caras livres
10b. Caras livres: ['col', 'abe'] 

0. Caras livres: ['col', 'abe']
1. Homem a fazer a proposta: col
2. Preferencias de col: ['dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan']
3. Pega a primeira preferencia de col que eh: dee
4. dee esta noiva? - Resposta: None
5a. dee esta livre
5b. col esta noivo de dee 

0. Caras livres: ['abe']
1. Homem a fazer a proposta: abe
2. Preferencias de abe: ['ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay']
3. Pega a primeira preferencia de abe que eh: ivy
4. ivy esta noiva? - Resposta: dan
6a. ivy esta noiva de dan
6b. Pega a lista de preferencias de ivy
6c. As preferencias de ivy são 
 ['ian', 'col', 'hal', 'gav', 'fred', 'bob', 'abe', 'ed', 'jon', 'dan']
6d. Posição do noivo atual dan: 9
6e. Posição da proposta atual abe: 6
7a. ivy prefere o novo cara abe
7b. ivy largou dan pra ficar com abe
8a. Pega as preferencias do dan
8b. dan pode tentar ['fay', 'dee', 'gay', 'hope', 'eve', 'jan', 'bea', 'cath', 'abi']
8c. dan vai para a lista de caras livres
8d. Caras livres ['dan'] 

0. Caras livres: ['dan']
1. Homem a fazer a proposta: dan
2. Preferencias de dan: ['fay', 'dee', 'gay', 'hope', 'eve', 'jan', 'bea', 'cath', 'abi']
3. Pega a primeira preferencia de dan que eh: fay
4. fay esta noiva? - Resposta: None
5a. fay esta livre
5b. dan esta noivo de fay 


In [7]:
print('\nNoivados')
engaged


Noivados
Out[7]:
{'abi': 'jon',
 'cath': 'bob',
 'hope': 'ian',
 'ivy': 'abe',
 'jan': 'ed',
 'bea': 'fred',
 'gay': 'gav',
 'eve': 'hal',
 'dee': 'col',
 'fay': 'dan'}

In [8]:
print('\nCasais:')
print('  ' + ',\n  '.join('%s esta noivo de %s' % couple
                          for couple in sorted(engaged.items())))


Casais:
  abi esta noivo de jon,
  bea esta noivo de fred,
  cath esta noivo de bob,
  dee esta noivo de col,
  eve esta noivo de hal,
  fay esta noivo de dan,
  gay esta noivo de gav,
  hope esta noivo de ian,
  ivy esta noivo de abe,
  jan esta noivo de ed

In [9]:
print('\nTeste de estabilidade dos noivados - PASSOU'
      if check(engaged) else 'Teste de estabilidade dos noivados - FALHOU')


Teste de estabilidade dos noivados - PASSOU

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]}')


Trocando dois noivados para introduzir um erro
abi esta noiva de fred
bea esta noiva de jon

In [11]:
print('\nCasais:')
print('  ' + ',\n  '.join('%s esta noivo de %s' % couple
                          for couple in sorted(engaged.items())))


Casais:
  abi esta noivo de fred,
  bea esta noivo de jon,
  cath esta noivo de bob,
  dee esta noivo de col,
  eve esta noivo de hal,
  fay esta noivo de dan,
  gay esta noivo de gav,
  hope esta noivo de ian,
  ivy esta noivo de abe,
  jan esta noivo de ed

In [12]:
print('\nTeste de estabilidade dos noivados - PASSOU'
      if check(engaged) else 'Teste de estabilidade dos noivados - FALHOU')


fred e bea gostam mais de si mesmos do que os seus atuais parceiros: abi e jon, respectivamente
Teste de estabilidade dos noivados - FALHOU

In [ ]: