[pyar] Un problema interesante

[Matías Bellone]

Carlos,

Aparentemente, tu problema es una generalización del "marriage pairing
algorithm" [1] comúnmente llamado el "hospital/resident problem" porque el
colegio de médicos de Estados Unidos lo usa para asignar residentes a sus
hospitales de preferencia [2].

Tu caso es ligeramente distinto porque:
* las opciones no "emiten" una preferencia
* necesitás sí o sí queden 4 equipos

Sin embargo, el algoritmo del NRMP te puede servir como base para
solucionar el problema. Lo que yo haría para esa adaptación sería:

* intentar asignar pX a su opción pY
   - si la opción no tiene 2 participantes, next X+1
   - si la opción tiene 2 participantes, intentar con la siguiente opción
      a) si agotamos todas las opciones (Y = 11), hacer backtracking al
participante anterior y asignar su siguiente opción (X-1, Y+1)
* si terminamos con más de 4 opciones incompletas, hacer backtracking al
participante anterior y asignar su siguiente opción

Otra alternativa es usar el algoritmo del NRMP generando listas de
preferencias aleatorias, o inclusive hacer una simulación montecarlo para
encontrar las versiones más óptimas (para algún valor de "óptimo") o
simplemente usar sus resultados como base para una solución más "dedística".

Saludos,
Toote

[1] https://en.wikipedia.org/wiki/Stable_marriage_problem
[2] https://www.youtube.com/watch?v=kvgfgGmemdA

On Wed, Sep 19, 2018 at 7:08 PM Carlos Matías <cmdelatorre en gmail.com> wrote:

> A ver si me ayudan a resolver esto (no es "ejercicio de la facu", es un
> problema de la vida real que tengo que resolver):
>
>  * Tengo 12 opciones: x0;...;x11
>  * Tengo 8 personas: p0;...;p7
>  * Cada persona emite sus preferencias de opciones (entre 1 y 12):
>       - pref_p0 = [x_0_0,...,x_0_n0]
>       - pref_p1 = [x_1_0,...,x_1_n1]
>       - pref_p2 = [x_2_0,...,x_2_n2]
>       - etc
> Como resultado, tengo que hacer dos cosas:
>  * elegir 4 opciones ganadoras: xA, xB, xC, xD
>  * Asignar equipos (disjuntos) de 2 personas, a cada opción ganadora,
> idealmente logrando que ambas personas del equipo tengan a la opción
> ganadora entre sus preferencias.
>
> O sea, por ejemplo, si la opción ganadora xA fue asignada al equipo (pI,
> pJ) entonces tanto pI como pJ tenían a xA entre sus preferencias.
>
> Cualquier corner case o cosas rara (por ejemplo si hay casos que no tienen
> solución), no importa. Que explote.
>
> Python-code, pseudo-código y texto se aceptan ;-)
>
> También me sirve saber si existe un algoritmo "con nombre y apellido" que
> resuelve el problema (respuestas del tipo: "clásico problema de matching",
> "eso es coloreo de grafos", "búsqueda binaria en árboles balanceados",
> "Aplicá Kruscal en un grafo acíclico dirigido multinivel sin ciclos" pero
> sin trollear porfa) Pero en ese caso también voy a necesitar que me lo
> expliquen ;-)
>
>
> Carlos Matías
> @py_litox <https://twitter.com/py_litox>
> _______________________________________________
> Lista de Correo de PyAr - Python Argentina - pyar en python.org.ar
> Sitio web: http://www.python.org.ar/
>
> Para administrar la lista (o desuscribirse) entrar a
> http://listas.python.org.ar/listinfo/pyar
>
> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
> Argentina - http://www.usla.org.ar
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20180919/2d35aa16/attachment.html>