Dados un cierto número de hombres y mujeres heterosexuales, organízalos por parejas de tal manera que su matrimonio sea estable. Cada persona ha ordenado a las personas del sexo opuesto según su preferencia. Los matrimonios se consideran estables si no es posible encontrar dos personas del sexo opuesto que se atraigan entre sí más que lo que les atraen sus respectivas parejas.
Este problema siempre tiene solución (¡a veces puede tener varias!) y existe un algoritmo, diseñado por David Gale and Lloyd Shapley en 1962, en el que las parejas se ordenan a sí mismas, como un sistema complejo. Mira en qué consiste el algoritmo en este vídeo:
In [ ]:
from IPython.display import HTML
HTML('<iframe src="http://youtube.com" width="700" height="400"></iframe>')
Nota: Este ejercicio sigue la nomenclatura y la estructura clásicas de este problema para que resulte intuitivo y fácil de seguir, no pretende ser un modelo real de comportamiento. Desde la organización de la PyConEs y nosotros mismos, queremos fomentar y apoyar la diversidad y la tolerancia en todas las facetas de la sociedad, y respetamos por igual todas las identidades de género y sexualidad.
In [1]:
import numpy as np
import random as random
In [2]:
class Woman (object):
''' Este es el elemento estático, quien recibe propuestas y elige al mejor'''
def __init__(self, name):
self.name = name
self.preferences = {}
self.preferences_inv = {}
self.boyfriend = []
self.candidates = []
def engage(self, man):
self.boyfriend = man
man.girlfriend = self
def breakup(self, man):
self.boyfriend = []
man.girlfriend = []
class Man (object):
'''Este es el elemento dinámico, que busca a su mejores opciones y se propone'''
def __init__(self, name):
self.name = name
self.preferences = {}
self.preferences_inv = {}
self.girlfriend = []
self.number_of_proposals = 1
def propose(self, woman):
woman.candidates += [self]
self.number_of_proposals += 1
Ahora creamos nuestra población, y la repartimos en dos listas.
In [3]:
magdalena, elena, ana, julia, marta = Woman('Magdalena'), Woman('Elena'), Woman('Ana'), Woman('Julia'), Woman('Marta')
carlos, siro, manuel, antonio, javier = Man('Carlos'), Man('Siro'), Man('Manuel'), Man('Antonio'), Man('Javier')
women = [magdalena, elena, ana, julia, marta]
men =[carlos, siro, manuel, antonio, javier]
In [4]:
for woman in women:
#Generamos una lista de preferencias de manera aleatoria
preferences = [ii for ii in range(1, len(men)+1)]
random.shuffle(preferences)
#Estas preferencias se almacenan como dos diccionarios
for index in range(len(men)):
woman.preferences[preferences[index]] = men[index]
for index in range(1, len(men)+1):
woman.preferences_inv[woman.preferences.get(index).name] = index
for man in men:
preferences = [ii for ii in range(1, len(women)+1)]
random.shuffle(preferences)
for index in range(len(women)):
man.preferences[preferences[index]] = women[index]
for index in range(1, len(men)+1):
man.preferences_inv[man.preferences.get(index).name] = index
In [5]:
def noche_de_fiesta(man, women):
for woman in women:
woman.candidates=[]
for man in men:
if man.girlfriend == []:
man.propose(man.preferences[man.number_of_proposals])
for woman in women:
if woman.boyfriend == []:
for ii in range(1, len(men)+1):
if woman.preferences[ii] in woman.candidates:
woman.engage(woman.preferences[ii])
break
elif any (woman.preferences_inv[man.name]>woman.preferences_inv[woman.boyfriend.name] for man in woman.candidates):
woman.breakup(woman.boyfriend)
for ii in range(1, len(men)+1):
if woman.preferences[ii] in woman.candidates:
woman.engage(woman.preferences[ii])
break
In [ ]:
for dia in range(1, len(men)+2):
print('Noche ' + str(dia))
print('-------')
noche_de_fiesta(men, women)
for woman in women:
print(woman.name)
if woman.candidates != []:
print(' Candidatos: ', [candidate.name for candidate in woman.candidates])
if woman.boyfriend != []:
print(' Novio: ', woman.boyfriend.name)
print()
print()
Este ejercicio parece un poco extraño, ¿no?
Pero... ¿y si te dijera que es un algoritmo muy utilizado diariamente por instituciones de todo el mundo?
Este algoritmo es muy usado para asignación de plazas en oposiciones, y se usa en varios países para repartir a los candidatos en las diferentes plazas según sus resultados y sus preferencias. Modelémoslo!
Crea unas clases nuevas llamadas 'Candidato' y 'Destino' basadas en 'Man' y 'Woman'. Simplemente con esto, ya tenemos un reparto de plazas muy adecuado, pero podemos mejorar nuestro modelo. Te sugiero que intentes los siguientes cambios:
Recuerda que es probable que necesites modificar las funciones anteriores (o crear otras nuevas basadas en ellas, si quieres conservar las originales sin tocar como referencia).
Para crear la población, puede que te resulte útil el método append() en el interior de un bucle.
In [ ]:
In [ ]:
Carlos Dorado, Aeropython, 20 de Noviembre de 2015
In [ ]: