[pyar] Un problema interesante

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


On Thu, Sep 20, 2018 at 1:36 AM Daniel Moisset <dmoisset en machinalis.com>
wrote:

> 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"
>
> On Wed, 19 Sep 2018, 23:19 Daniel Moisset, <dmoisset en machinalis.com>
> wrote:
>
>> 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"
>>
>>
>> On Wed, 19 Sep 2018, 17:08 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
>>
>> _______________________________________________
> 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/20180920/6c8806ca/attachment.html>