Re: [Python-es] Re: Asignación de eventos en Python

[Joan Pallarès]

Hola,

Veo que nadie me conesta el mail anterior, da igual, olvidadlo. Ahora solo
quiero lo siguiente:

Tenemos una *lista de parejas*, creada así:
*parejas = [(1, 'a'), (1, 'b'), (1, 'c'), (1, 'd'),
                (2, 'a'), (2, 'b'), (2, 'c'),
                (3, 'a'), (3, 'b'), (3, 'c'), (3, 'd')]*

Queremos conseguir todas las *posibles combinaciones de numeros y
letras*sin que se repitan, por ejemplo:
*1a,2b,3c*    Esta sería una solución
*1a,2b,3d*    Otra posible solución
*1b,2a,3c*    Una más
etc.

No queremos conseguirlas todas las posibles soluciones de golpe, si no solo
una. Pero ha de guardar la informacion de la solucion de alguna manera para
luego poder pedir la siguiente solucion (o la anterior).* ¿Cómo lo haríais?
*

Yo he hecho un algortimo de backtraking que me obtiene la primera solución,
pero luego no se obtener las siguientes. Os los enseño:
*parejas = [(1, 'a'), (1, 'b'), (1, 'c'), (1, 'd'),
           (2, 'a'), (2, 'b'), (2, 'c'),
           (3, 'a'), (3, 'b'), (3, 'c'), (3, 'd')]
print parejas

listasCorrectas = []
lista = []

def numerosDiferentes(lista,listasCorrectas):
    numeros = []
    letras = []
    for numero,letra in lista:
        numeros.append(numero)
        letras.append(letra)
    if len(numeros) == len(set(numeros)) and len(letras) ==
len(set(letras)):
        return True
    return False


def backTracking(parejas,lista,listasCorrectas):
    if len(lista) == 3 and numerosDiferentes(lista,listasCorrectas):
        listasCorrectas.append(lista)
        print 'LISTA CORRECTA',lista
        return

    if len(lista) < 2:
        lista.append(parejas[0])
        print lista
        backTracking(parejas[1:],lista)

    while(not numerosDiferentes(lista) and len(lista)>1):
        lista = lista[:-1]


    lista.append(parejas[0])
    print lista
    backTracking(parejas[1:],lista)

backTracking(parejas,lista)*

2008/7/9 Joan Pallarès <joan.pallares en gmail.com>:

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