Re: Re: Asignación de eventos en Python

[Joan Pallarès]

Comprobado

He copiado tu código tal cual y me devuelve:

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

fenómenos paranormales? no creo, debe ser el compilador o que se te ocurre?
tengo Python 2.5, y lo ejecuto desde Eclipse bajo Windows XP (no me
critiqueis mucho xD)

Saludos

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

> He copiado y pegado tu codigo y solo he añadido que imprima solucion
> delante de cada solucion y que imprima la matriz al final. Bueno y por no
> cambiar la lista de parejas y puesto un diccionario, así:
>
> *def parejasAMatriz(p) :
>    # genera la matriz a partir de la lista de parejas
>    dict = {'a':1,'b':2,'c':3,'d':4}
>    nfilas = max([i[0] for i in p])
>    ncols = max([i[1] for i in p])
>    NUMncols = dict[ncols]
>    m = [ list([0]*NUMncols) for i in xrange(nfilas) ]
>    for f, c in p :
>        m[f-1][dict[c]-1] = 1
>    return m*
>
> y me imprime lo que te he puesto antes:
> Solucion [0, 1, 2]
> Solucion [0, 1, 3]
> [[1, 1, 1, 1], [1, 1, 1, 0], [1, 1, 1, 1]]
>
> Debo haber cambiado algo mientras copiaba y pegaba, no valgo ni para eso
> xD......:
>
> Entiendo perfectamente lo que es backtracking, y sí, es una buena idea lo
> que me dices de las funciones next y prev pero en el caso real que voy a
> utilizar este algoritmo sera una matriz de 100x100 o incluso más y no se si
> será del todo eficiente calcular todas las soluciones de golpe. Sería mejor
> generar una a una según las pidiera el usuario (pero claro no se hacerlo).
> Aunque quizá con este sistema de la matriz es muy rápido y lo puedo calcular
> todo de golpe. Pero bueno primero tengo que conseguir que me funcione con
> este caso sencillo y luego adaptarlo al grande.
>
> Pongo todo el código que me devuelve lo que he dicho antes, que puede pasar
> para que no nos devuelva lo mismo?:
>
> *parejas = [(1, 'a'), (1, 'b'), (1, 'c'), (1, 'd'),
>            (2, 'a'), (2, 'b'), (2, 'c'),
>            (3, 'a'), (3, 'b'), (3, 'c'), (3, 'd')]
>
>
> def parejasAMatriz(p) :
>    # genera la matriz a partir de la lista de parejas
>    dict = {'a':1,'b':2,'c':3,'d':4}
>    nfilas = max([i[0] for i in p])
>    ncols = max([i[1] for i in p])
>    NUMncols = dict[ncols]
>    m = [ list([0]*NUMncols) for i in xrange(nfilas) ]
>    for f, c in p :
>        m[f-1][dict[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 'Solucion',s
> print parejasAMatriz(parejas)*
>
> Voy a la cama que mañana toca madrugar. Muchas gracias Alexis
>
> Saludos
>
> 2008/7/23 Alexis Roda <alexis.roda.villalonga en gmail.com>:
>
> En/na Joan Pallarès ha escrit:
>>
>>> Hola,
>>>
>>> Muchas gracias con tu ayuda. Aunque me interesa alguna forma "más
>>> elegante"
>>> de volver atrás"
>>>
>>
>> En backtracking, volver atrás no significa encontrar la solución
>> "anterior" (que me parece que es lo que quieres) sino retroceder,
>> deshaciendo el último "cambio" y probando otra posibilidad para encontrar la
>> "siguiente" solución.
>>
>>
>> Para lo que (creo que) quieres solo tienes que implementa una clase con
>> dos metodos, prev y next, una lista que almacene las soluciones encontradas
>> hasta el momento y el indice de la "solución actual". Si al llamar a next no
>> quedan "soluciones anteriores" se calcula una nueva solución y se almacena
>> en la lista.
>>
>> class Soluciones :
>>    def __init__(self, parejas) :
>>        self._encontrado = []
>>        self._indice = 0
>>        matr = parejasAMatriz(parejas)
>>        self._generador = iter(generaSoluciones(matr))
>>
>>    def next(self) :
>>        if self._indice >= len(self._encontrado) :
>>            self._encontrado.append(list(self._generador.next()))
>>        self._indice += 1
>>        return self._encontrado[self._indice - 1]
>>
>>    def prev(self) :
>>        if self._indice <= 0 :
>>            return None
>>        self._indice -= 1
>>        return self._encontrado[self._indice]
>>
>> Deberías añadir alguna comprobación extra para el caso que se agoten todas
>> las soluciones y asegurarte que las comprobaciones que hace son correctas.
>>
>>
>>  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]]
>>>
>>
>> No entiendo de donde sale la última linea. Mi código no imprime la matriz!
>>
>>  por lo que no hace bactracking, no?
>>>
>>
>> El bucle "while not disponible[fila]" implementa el retroceso: si no
>> quedan posibilidades para una posición retrocede una posición para seguir
>> probando.
>>
>>  te has olvidado algo? o yo me he dejado algo?
>>>
>>
>> Al ejecutarlo me imprime:
>>
>> [0, 1, 2]
>> [0, 1, 3]
>> ...
>> [3, 2, 0]
>> [3, 2, 1]
>>
>>
>>
>>
>> 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