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

[Joan Pallarès]

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
>