Re: Re: Asignación de eventos en Python

[Joan Pallarès]

Hola,

Siento mucho haber enviado el programa sin que se pudiera ejecutar.

Muchas gracias con tu ayuda. Aunque me interesa alguna forma "más elegante"
de volver atrás"

acabo de usar tu codigo y me escupe esto:

Solucion [0, 1, 2]
Solucion [0, 1, 3]
[[1, 1, 1, 1], [1, 1, 1, 0], [1, 1, 1, 1]]

por lo que no hace bactracking, no?

te has olvidado algo? o yo me he dejado algo?

¿Alguien tiene alguna idea más?

Saludos y gracias


2008/7/18 Alexis Roda <alexis.roda.villalonga en gmail.com>:

> En/na Joan Pallarès ha escrit:
>
> Antes de responder me gustaría hacer un comentario.
>
> Si mandas un programa a la lista en busca de ayuda al menos deberías
> verificar que funciona (el tuyo da error con el paso de parámetros). Si
> alguien se toma la molestia de probar el programa y ve que no funciona lo
> más probable es que ignore tu mensaje.
>
>
>  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?
>>
>
> Lo de la "anterior" lo veo mas complicado. Deberás guardar las soluciones
> encontradas en algún sitio para poder "volver" a las anteriores.
>
>  Yo he hecho un algortimo de backtraking que me obtiene la primera
>> solución,
>> pero luego no se obtener las siguientes.
>>
>
> Al algoritmo que propones le falta la parte del "back" para ser
> backtracking. Cuando has encontrado la solución con (3, 'd') debes seguir
> probando. Como no hay más posibilidades con el 3 vuelves atrás y pruebas a
> partir de [(1, 'a'), (2, 'c')], luego a partir de [(1, 'b')] etc.
>
> Backtracking es una manera fina de decir fuerza bruta. Siempre que utilices
> backtracking tienes que poner mucho cuidado en reducir el tamaño del espacio
> de búsqueda, en caso contrario el problema se vuelve rápidamente inmanejable
> (computacionalmente hablando) y siendo python un lenguaje interpretado
> cualquier optimización es interesante.
>
> Tal como planteas el problema no aprovechas que si has elegido (1, 'a')
> como primer elemento de la solución ninguna pareja con 1 o 'a' es aceptable.
> Por tanto estas comprobando muchas combinaciones que no son solución.
>
> Creo que hay una forma mejor de plantear/visualizar el problema que elimina
> las combinaciones que no son solución.
>
> La lista del ejemplo puede representarse matricialmente como:
>
>  a  b  c  d
> 1 1  1  1  1
> 2 1  1  1  0
> 3 1  1  1  1
>
> donde un 1 en una casilla significa que la pareja aparece en la lista y un
> 0 que no aparece.
>
> Visto así el problema se reduce a escoger tres celdas de la matriz sin
> repetir fila ni columna. Algo parecido al problema de las 8 reinas, pero sin
> tener en cuenta las diagonales y con casillas que no son válidas.
>
> Una asignación puede representarse mediante una lista de caracteres: por
> ejemplo ['a', 'b', 'c'] representa la asignación (1, 'a'), (2, 'b'), (3,
> 'c'); ['b', 'a', 'd'] corresponde a (1, 'b'), (2, 'a'), (3, 'd') etc.
>
> Como tienes que elegir una celda de cada columna, sin repetir columna, una
> solución estará formada por tres letras distintas.
>
> No todas las listas con tres letras distintas corresponden a asignaciones
> válidas, p.e. ['a', 'd', 'b'] no es válida ya que la pareja (2, 'd') no
> aparece en la lista.
>
>
>
> Todo este rollo se resume en el siguiente programa (no muy pythonico).
>
> # por simplicidad la segunda componente se codifica mediante un
> # numero. 1 -> 'a', 2 -> 'b' etc.
>
> parejas = [(1, 1), (1, 2), (1, 3), (1, 4),
>           (2, 1), (2, 2), (2, 3),
>           (3, 1), (3, 2), (3, 3), (3, 4),
>           ]
>
> def parejasAMatriz(p) :
>    # genera la matriz a partir de la lista de parejas
>    nfilas = max([i[0] for i in p])
>    ncols = max([i[1] for i in p])
>    m = [ list([0]*ncols) for i in xrange(nfilas) ]
>    for f, c in p :
>        m[f-1][c-1] = 1
>    return m
>
> def genDisponible(m, e, p) :
>    # a partir de la matriz y una solucion parcial devuelve una lista
>    # con las columnas disponibles para una fila determinada
>    ncols = len(m[0])
>    res = []
>    for i in xrange(ncols) :
>        if i not in e and m[p][i] :
>            # la columna esta disponible y la asignacion es valida
>            res.append(i)
>    return iter(res)
>
>
> def generaSoluciones(p) :
>    matriz = parejasAMatriz(p)
>    nfilas = len(matriz)
>    ncols = len(matriz[0])
>    estado = [-1] * nfilas
>    disponible = [ None ] * nfilas
>    fila = 0
>    disponible[fila] = iter(range(ncols))
>    while True :
>        while not disponible[fila] :
>            estado[fila] = -1
>            fila -= 1     # retrocede
>            if fila < 0 : # no hay mas soluciones
>                raise StopIteration()
>        estado[fila] = disponible[fila].next()
>        fila += 1
>        if fila >= nfilas :
>            yield estado
>            fila -= 1
>        else :
>            disponible[fila] = genDisponible(matriz, estado, fila)
>
>
> for s in generaSoluciones(parejas) :
>    print s
>
> Espero que te sirva.
>
>
>
>
> Saludos
>
> _______________________________________________
> 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