[pyar] Un problema interesante

[Carlos Matías]

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>

[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]

Post by Carlos Matías
A ver si me ayudan a resolver esto (no es "ejercicio de la facu", es un
* Tengo 12 opciones: x0;...;x11
* Tengo 8 personas: p0;...;p7
- 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
* 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>
_______________________________________________
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

[ASo]

*Este problema parece ser similar a buscar combinaciones de palabras entre
documentos.*

*Hay mucho código python para resolverlo.*

*Se trata de hallar la matriz de co-ocurrencias.*

Post by Carlos Matías
A ver si me ayudan a resolver esto (no es "ejercicio de la facu", es un
* Tengo 12 opciones: x0;...;x11
* Tengo 8 personas: p0;...;p7
- 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
* 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>
_______________________________________________
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

[Juan Antonio Alvarez]

Disclaimer: No tengo la mas remota idea de como resolverlo

Pero solo por curiosidad, los n0-7 de las preferencias, son arbitrarios de
0-12 o tienen algún tipo de limitación? El orden de las preferencias tienen
algún peso? Si lo puse en la posición 0 lo prefiero mas que al de la
posición 3?

Juan

Post by Carlos Matías
A ver si me ayudan a resolver esto (no es "ejercicio de la facu", es un
* Tengo 12 opciones: x0;...;x11
* Tengo 8 personas: p0;...;p7
- 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
* 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>
_______________________________________________
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

[Carlos Matías]

Juan,

* los n0-7 de las preferencias *efectivamente* son arbitrarios
* no hay peso ni orden en las preferencias

Salut


Carlos Matías
@py_litox <https://twitter.com/py_litox>

Post by Juan Antonio Alvarez
Disclaimer: No tengo la mas remota idea de como resolverlo
Pero solo por curiosidad, los n0-7 de las preferencias, son arbitrarios de
0-12 o tienen algún tipo de limitación? El orden de las preferencias tienen
algún peso? Si lo puse en la posición 0 lo prefiero mas que al de la
posición 3?
Juan

Post by Carlos Matías
A ver si me ayudan a resolver esto (no es "ejercicio de la facu", es un
* Tengo 12 opciones: x0;...;x11
* Tengo 8 personas: p0;...;p7
- 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
* 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>
_______________________________________________
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

_______________________________________________
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

[Daniel Moisset]

Los números esos (8, 12) son reales? Si es así y tenés el input acotado, el
problema es O(1) y es trivial =P

Un poco más en serio, con esos y de input, un approach de fuerza bruta
debería poder cubrir todas las selecciones de opciones × asignaciones a
grupos bastante rápido (una cuenta rápida me dice que son ~2.5 millones) Y
si exploras con alguna heurística astuta (por ej asignar las opciones más
populares primero) seguramente podes obtener un early exit si hay solución
(si no hay, vas a explorar todo)

Si las cantidades reales de opciones/personas son más grandes, o sí tenés
que hacer esto muchísimas veces. probablemente se puede explorar cosas más
"fancy"

Post by Carlos Matías
A ver si me ayudan a resolver esto (no es "ejercicio de la facu", es un
* Tengo 12 opciones: x0;...;x11
* Tengo 8 personas: p0;...;p7
- 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
* 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>
_______________________________________________
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

[Daniel Moisset]

Y pensando un ratito más, alcanza con solo fuerzabrutear la selección de
opciones ganadoras que son 12!/(8!4!) = 495.

Para cada combinación candidato de opciones ganadoras, podes correr un
algoritmo de matching (ej: Karp, o lo que te provea algún paquete tipo
networkx), dónde generas un clon del vértice correspondiente a cada una de
las 4 ganadoras para que te refleje el aspecto de "cada opción asignada a 2
personas"

Post by Daniel Moisset
Los números esos (8, 12) son reales? Si es así y tenés el input acotado,
el problema es O(1) y es trivial =P
Un poco más en serio, con esos y de input, un approach de fuerza bruta
debería poder cubrir todas las selecciones de opciones × asignaciones a
grupos bastante rápido (una cuenta rápida me dice que son ~2.5 millones) Y
si exploras con alguna heurística astuta (por ej asignar las opciones más
populares primero) seguramente podes obtener un early exit si hay solución
(si no hay, vas a explorar todo)
Si las cantidades reales de opciones/personas son más grandes, o sí tenés
que hacer esto muchísimas veces. probablemente se puede explorar cosas más
"fancy"

Post by Carlos Matías
A ver si me ayudan a resolver esto (no es "ejercicio de la facu", es un
* Tengo 12 opciones: x0;...;x11
* Tengo 8 personas: p0;...;p7
- 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
* 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>
_______________________________________________
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

[Carlos Matías]

¡Gracias a todos los que respondieron!

Darni: efectivamente los números son esos, por lo que fuerzabrutear anda.
Incluso mirarlo un poco a ojo alcanza ;-)
Lo mismo me parecía interesante generalizarlo como puro ejercicio y para
ver con cuál de las opciones que me pasaron me pongo a jugar.

De nuevo, gracias a todos

Carlos Matías
@py_litox <https://twitter.com/py_litox>

Post by Daniel Moisset
Y pensando un ratito más, alcanza con solo fuerzabrutear la selección de
opciones ganadoras que son 12!/(8!4!) = 495.
Para cada combinación candidato de opciones ganadoras, podes correr un
algoritmo de matching (ej: Karp, o lo que te provea algún paquete tipo
networkx), dónde generas un clon del vértice correspondiente a cada una de
las 4 ganadoras para que te refleje el aspecto de "cada opción asignada a 2
personas"

Post by Daniel Moisset
Los números esos (8, 12) son reales? Si es así y tenés el input acotado,
el problema es O(1) y es trivial =P
Un poco más en serio, con esos y de input, un approach de fuerza bruta
debería poder cubrir todas las selecciones de opciones × asignaciones a
grupos bastante rápido (una cuenta rápida me dice que son ~2.5 millones) Y
si exploras con alguna heurística astuta (por ej asignar las opciones más
populares primero) seguramente podes obtener un early exit si hay solución
(si no hay, vas a explorar todo)
Si las cantidades reales de opciones/personas son más grandes, o sí tenés
que hacer esto muchísimas veces. probablemente se puede explorar cosas más
"fancy"

Post by Carlos Matías
A ver si me ayudan a resolver esto (no es "ejercicio de la facu", es un
* Tengo 12 opciones: x0;...;x11
* Tengo 8 personas: p0;...;p7
- 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
* 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>
_______________________________________________
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

_______________________________________________

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