Re: Re: Asignación de eventos en Python

[Joan Pallarès]

Hola,

Muchas gracias por contestar,
lo explicaré con más detalle:

Tengo una *lista de partidos* y una *lista árbitros.*
Hay más árbitros que partidos.
Hay una *serie de filtros* que hacen que algunos árbitros no puedan hacer
algunos partidos.
Hasta ahora calculaba *una sola solución*, es decir, *una serie de
asignaciones partido-arbitro donde se respetaban los filtros*

Necesito cacular* todas las posibles soluciones*

Para esto, antes de que me contestaráis el mail estuve investigando y pensé
que mi problema tenía mucho que ver con la teoría de conjuntos. Tengo dos
conjuntos (árbitros y partidos) y quiero todas su posibles combinaciones.

Entonces descubrí el producto cartesiano (
http://es.wikipedia.org/wiki/Producto_cartesiano) y lo he aplicado de la
siguiente manera:
*[(partido,arbitro) for partido in partidos for arbitro in arbitros if
self.pasaFiltros(partido,arbitro)]*

Donde hago el mencionado producto cartesiano pero aplicando los filtros. Me
funciona y ahora tengo una lista de parejas partido-árbitro con todas
posibilidades. En el ejemplo que uso tengo 54 partidos y 70 árbitros, esto
da 3780 (justo el producto) si aplico filtros se reduce esta cantidad.

Para que os hagáis una idea de cómo es la lista, sería así:

Partidos: 1, 2 ,3
Árbitros: a, b, c, d

Lista:
1 a
1 b
1 d (no aparece el árbitro c porque ese dñia tiene fiesta)
2 a
2 b
2 c
2 d
3 a
3 b
3 c
3 d

Mi problema ahora es como sacar de esta lista interminable las posibles
asignaciones/jornadas. En el ejemplo serían posibles jornadas:

1a,2b,3c
1b,2a,3c

Necesitaría sacarlas ordenadamente. Un posible usuario ve una jornada, no le
gusta, pasa a la siguiente tampoco le gusta, vuelve a la anterior y se queda
con ella. Navegar por las soluciones

He pensado en "buscar en profundidad" parecido al DepthFirst de los árboles.
Si usará el algoritmo este que iamino con el ejemplo quedaría:
1a 2b 3c
1a 2b 3d
1a 2c 3b No hay mas soluciones en el "tercer nivel" subo al "segundo nivel"
1a 2c 3d
1a 2d 3b
.....

¿os parece buena ida?
¿leeríais de otra forma lo obtenido mediantes el producto cartesiano?
Lo haríais todo de otra manera?

2008/7/8 Francisco Palm <francisco.palm en gmail.com>:

> [arbitro for arbitro in arbitros if X and Y and Z]
> Donde X, Y y Z son las condiciones, por ejemplo:
> not(arbitro.repetido) and not(arbitro.asignado) and not(arbitro.indeseado)
>
> Si das más información es posible atender tu consulta mejor... Escribo
> esto para que deduzcas que hay cosas que no se pueden conocer del
> problema con lo que has dicho.
>
> Saludos
>
> F. Palm
>
> On 7/7/08, Joan Pallarès <joan.pallares en gmail.com> wrote:
> > Hola,
> >
> > Estoy desarrollando una aplicación en Python para asignar árbitros a
> > partidos de fútbol dependiendo de un filtros (no puede repetir partido,
> etc)
> >
> > Ahora solo calculo la primera opción válida. Me gustaría calcular todas
> las
> > posibles opciones, (o ser capaz de calcularlas si el usuario lo
> quisiera).
> >
> > Por ejemplo: el usuario obtiene un resultado que pasa todos los filtros
> pero
> > no le gusta y quiere ver la siguiente posibilidad
> >
> > Estoy buscando algoritmos que me permitan calcular todas las opciones
> pero
> > no encuentro.
> >
> > He encontrado "Búsqueda Tabu" pero no me sirve para este caso
> >
> > Sería un algoritmo para relaciones entre conjuntos o algo por el estilo,
> no?
> >
> > ¿Alguna idea?
> >
> > Saludos
> > _______________________________________________
> > Lista de correo Python-es
> > http://listas.aditel.org/listinfo/python-es
> > FAQ: http://listas.aditel.org/faqpyes
> >
>
>
> --
> --------------------------------------
> fpalm en ula.ve
> francisco.palm en gmail.com
>
> cel: 0414 5109177
> tel: 0274 6352001
>
> ----
> Yo creo que todavía no es demasiado tarde para construir una utopía
> que nos permita compartir la tierra. Gabriel García Márquez.
> _______________________________________________
> Lista de correo Python-es
> http://listas.aditel.org/listinfo/python-es
> FAQ: http://listas.aditel.org/faqpyes
>
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes