Vamos começar pelo exemplo do problema que não tem solução estável. Suponha que existam quatro garotos: A, B, C e D. Cada um deles com as preferências:
A = (B>C>D)
B = (C>A>D)
C = (A>B>D)
D = (A>B>C)
Provaremos que todos os pareamentos possíveis são instáveis.
Vamos começar com o pareamento inicial AB, CD. A prefere B, então está satisfeito. B, no entanto, prefere C. Como C também prefere B a D, os pareamentos não são estáveis.
Testando o segundo pareamento possível, AC, BD. A prefere B a C, e C prefere A a D, então o pareamento não é estável.
Testando o terceiro pareamento possível, AD, BC. A prefere C a D, e C prefere A a D, então o pareamento não é estável.
Assim, nenhum dos pareamentos é estável, o que gera circularidade.
Dessa forma, a solução não existe quando um dos garotos é a última escolha de todos os outros, o que chamaremos de stinky roomate condition. Assim, qualquer tentativa de ordenamento deve primeiro testar se essa condição não ocorre.
Em primeiro lugar, é necessário importar as bibliotecas que utilizaremos no exercício:
import pandas as pd
import numpy as np
import random
import math
from joblib import Parallel,delayed
Em seguida, vamos criar um gerador de preferências aleatórias dependente do número de garotos e gerar notas para os garotos dependendo de sua posição na preferência dos demais garotos. Minha ideia aqui é que se os garotos melhor posicionados proporem primeiro, a chance de serem os preferidosé maior, então gera menos iterações. Além disso, a nota permite identificar o caso do stiny roomate, que terá sempre nota zero.
Agora, vamos fazer a primeira rodada de pareamento: o garoto com maior nota (garotoX) propõe dividir quarto com o primeiro da lista de preferências dele (garotoY).
Se o garoto que recebeu a proposta não tem roommate, ele aceita a proposta. Se o garotoY já tem um roommate, ele verifica se o garotoX está melhor colocado em sua lista de preferências. Se estiver, ele troca de roommate. Se não estiver, ele nega, e o garotoX propõe para o próximo garoto de sua lista.
Toda vez que há um pareamento novo, ou seja, uma proposta é aceita, é necessário alocar os garotos como roommates um do outro, descartar os roommates antigos e sinalizar que houve uma mudança, dado que o código termina se passar por todas as preferências e ninguém quiser trocar, indicando que os pareamentos são estáveis.
Além disso, é necessário indicar quem recebeu a proposta de quem. A ideia aqui é que quem recebeu a proposta descarta das suas preferências todos os garotos com avaliação pior, dado que ele não vai trocar um garoto melhor por um pior. Se no processo de descarte algum garoto ficar com preferência vazia, isso é um sinal de que não há equilíbrio possível. Após o descarte das preferências, roda-se o algoritmo novamente, tentando parear os garotos.
Assim, o algoritmo tem três saídas: stinky roomate, pareamentos estáveis, e circularidade por preferência vazia.
Vou colocar todo esse processo em uma função que depende apenas do número de garotos:
#Vamos criar uma função que depende apenas do número de garotos
def roomate_pairing(numero_garotos):
lista_garotos = range(0,numero_garotos)
print(lista_garotos)
class erro1(Exception):
"""Erro: número de garotos deve ser par"""
pass
# Vamos estabelecer uma função que atribua, a cada garoto,
# uma lista de preferência para os demais garotos, isto é,
# a lista de prefeência deve ser aleatória e incluir todos
# os garotos menos ele mesmo.
def generate_preference(lista_garotos,garoto):
if (len(lista_garotos) % 2) == 0:
pass
else:
raise erro1('numero impar de garotos')
new_list = []
new_list = lista_garotos[:]
del new_list[garoto]
random.shuffle(new_list)
return new_list
# Teste para o garoto número 1 da lista:
a = generate_preference(lista_garotos,1)
print a
# Neste caso, o primeiro da lista é o mais preferido e assim sucessivamente.
#Agora vamos criar um dicionário que associa a cada garoto
#a sua lista de preferências.
preferencias_temp = {}
for garoto in lista_garotos:
preferencias_temp.update({garoto:generate_preference(lista_garotos,garoto)})
#vamos criar uma matriz em que cada garoto é uma coluna, com suas preferências.
preferencias_df = pd.DataFrame(preferencias_temp)
#nomeando as colunas
preferencias_df.columns = 'garoto_' + preferencias_df.columns.astype(str)
#vamos criar uma função que já crie essa matriz a partir do número de garotos
def create_preferences_df(numero_garotos):
lista_garotos = range(0,numero_garotos)
preferencias_temp = {}
for i in lista_garotos:
preferencias_temp.update({i:generate_preference(lista_garotos,i)})
preferencias_df = pd.DataFrame(preferencias_temp)
preferencias_df.columns = 'garoto_' + preferencias_df.columns.astype(str)
preferencias_df = 'garoto_' + preferencias_df.astype(str)
return preferencias_df
preferences_df = create_preferences_df(numero_garotos)
#vamos agora criar um dicionário para as notas
total_grades = {}
for garoto in preferences_df.columns:
total_grades.update({garoto:0})
total_grades
#vamos definir a nota máxima como o numero de linhas menos um.
#Para cada garoto X nas colunas, vamos acessar a lista de preferências.
#Em seguida, vamos somar as notas dos demais garotos à nota conferida pelo garoto X
max_score = preferences_df.shape[0] - 1
for garoto in preferences_df.columns:
preference_series = preferences_df.loc[:,garoto]
for rank in preference_series.index:
total_grades[preference_series[rank]] = total_grades[preference_series[rank]] + max_score - rank
#Vamos criar um dicionario conjugado
temp_dict = {'garoto':total_grades.keys(),'notas':total_grades.values(),'roommate':numero_garotos*[''],'proposed_by':numero_garotos*['']}
temp_dict
#vamos criar um data frame de pareamento_df
pareamento_df_original = pd.DataFrame(temp_dict)
pareamento_df_original = pareamento_df_original[['garoto','notas','roommate','proposed_by']]
#vamos verificar a lista de alunos por grau de desejabilidade
pareamento_df_original = pareamento_df_original.sort_values(by='notas', ascending=False).set_index('garoto')
pareamento_df_original
#vamos fazer um processo iterativo de pareamento,
#em que o garoto que faz a proposta é o que possui
#a maior nota entre os que náo tem roomates
pareamento_df_final=pareamento_df_original.copy()
#sinalizador se esta estavel
mudou = False
#Vamos excluir o caso em que haja algum aluno com nota zero, ou seja, o caso do stinky roomate
if (pareamento_df_original.notas==0).sum()>0:
return ('problema não tem solução pelo caso do stinky roomate')
#enquanto houver algum garoto sem roomate
while ((pareamento_df_final.loc[:,'roommate']=='').any() | mudou==True):
mudou=False
for garotoX in pareamento_df_final.index:
#criar um vetor de preferências desse garoto
preferences_garotoX=preferences_df.loc[:,garotoX]
if pareamento_df_final.loc[garotoX,'roommate']=='':
for garotoY in preferences_garotoX:
if garotoY != '':
#se o garotoY não tiver ninguém
if pareamento_df_final.loc[garotoY,'roommate']=='':
#ele aceita o garotoX e eles viram roomates um do outro
pareamento_df_final.loc[garotoY,'roommate']=garotoX
pareamento_df_final.loc[garotoX,'roommate']=garotoY
#todos os que tinham proposta do garotoX perdem a proposta
pareamento_df_final.loc[pareamento_df_final.loc[:,'proposed_by']==garotoX,'proposed_by']=''
#garotoY fica com a proposta do garotoX
pareamento_df_final.loc[garotoY,'proposed_by']=garotoX
#garotoX perde qualquer proposta que tinha
pareamento_df_final.loc[garotoX,'proposed_by']=''
#sinaliza que nesta rodada houve mudança
mudou=True
break
else:
#determinar qual o roommate atual nesta iteração
current_roommate_Y=pareamento_df_final.loc[garotoY,'roommate']
current_roommate_X=pareamento_df_final.loc[garotoX,'roommate']
# print('current_roommate_X =',current_roommate_X)
#criar um vetor de preferência do garoto Y
preferences_garotoY=preferences_df.loc[:,garotoY]
#verifica se o que está propondo é melhor que o atual, se sim, troca
if preferences_garotoY[preferences_garotoY==garotoX].index<preferences_garotoY[preferences_garotoY==current_roommate_Y].index:
#o roomate antigo do Y fica vazio, porque ele trocou
pareamento_df_final.loc[current_roommate_Y,'roommate']=''
#se o current roomate tiver sido proposto pelo garoto Y, ele também perde a proposta
pareamento_df_final.loc[current_roommate_Y,'proposed_by']=''
#garotoX e garotoY viram roomates
pareamento_df_final.loc[garotoY,'roommate']=garotoX
pareamento_df_final.loc[garotoX,'roommate']=garotoY
#todos os que tinham proposta do garotoX perdem a proposta
pareamento_df_final.loc[pareamento_df_final.loc[:,'proposed_by']==garotoX,'proposed_by']=''
#garotoY fica com a proposta do garotoX
pareamento_df_final.loc[garotoY,'proposed_by']=garotoX
#garotoX perde qualquer proposta que tinha
pareamento_df_final.loc[garotoX,'proposed_by']=''
#sinaliza que nesta rodada houve mudança
mudou=True
break
#Se o código rodou por todos os garotos e ninguem trocou, os pareamentos são estáveis
if mudou==False:
return('PAREAMENTOS SAO ESTAVEIS')
#Se o código rodou e alguém trocou, verificar se alguma preferência está vazia. Preferência vazia é sinal de que ão há convergência possível
else:
for garotoX in preferences_df:
if (preferences_df.loc[:,garotoX] == '').all():
return('nao ha equilibrio possivel')
# Os caras que receberam a proposta deletam de sua preferência todos os menos preferidos e os que são deletados deletam esse cara também
for garotoX in pareamento_df_final.index:
if pareamento_df_final.loc[garotoX,'proposed_by']=='':
pass
else:
#print(garotoX,'\n\n\n\n\n\n')
garoto_que_propos = pareamento_df_final.loc[garotoX,'proposed_by']
#criar um vetor de preferências desse garoto
preferences_garotoX=preferences_df.loc[:,garotoX].copy()
#deletar todos os que forem pior avaliados que o que propôs
#primeiro vamos identificar o índice do garoto que propôs nas preferências do garotoX
indice_da_proposta=preferences_garotoX[preferences_garotoX == garoto_que_propos].index.values[0]
#Verificar se o garoto que propôs não é o último na preferência do garoto X
if indice_da_proposta != preferences_df.index[-1]:
#Se ele não for o último, deletar todos os que são pior avaliados
preferences_df.loc[indice_da_proposta+1:,garotoX] = ''
#identificar quais garotos foram eliminados na etapa anterior
garotos_eliminados = preferences_garotoX[indice_da_proposta+1:]
#deletar o garotoX da preferência de todos os eliminados
for garoto_eliminado in garotos_eliminados:
#primeiro verificar se o garoto j'a não foi eliminado antes
if garoto_eliminado != '':
#atribuir valor zero aos garotos que foram deletados da preferência do garotoX
preferences_df.loc[preferences_df.loc[:,garoto_eliminado] == garotoX,garoto_eliminado] = ''
E, por último, vamos fazer rodar mil vezes para uma quantidade numero_garotos de garotos
e reportar qual o percentual das três soluções possíveis nas mil simulações
results = Parallel(n_jobs = 8, verbose = 10)(delayed(roomate_pairing)(numero_garotos) for numero_garotos in 1000*[8])
resulting_series = pd.Series(results)
resulting_series.value_counts()/resulting_series.shape[0]
Resultados de mil simulações para quatro garotos:
PAREAMENTOS SAO ESTAVEIS 0.855
problema não tem solução pelo caso do stinky roomate 0.145
Resultado de mil simulações para seis garotos:
PAREAMENTOS SAO ESTAVEIS 0.996
problema não tem solução pelo caso do stinky roomate 0.004
Resultado de mil simulações para dez garotos:
PAREAMENTOS SAO ESTAVEIS 0.99
nao ha equilibrio possivel 0.01
Resultado de mil simulações para 30 garotos:
PAREAMENTOS SAO ESTAVEIS 0.962
nao ha equilibrio possivel 0.038