Bienvenidos sean a este post, en el post anterior vimos un ejemplo de trabajo productor-consumidor que puede ser un patron practico de bucles iteradores: el iterador produce item para ser consumidos por el bloque del bucle, por lo tanto es apropiado usar corutinas como iteradores, de hecho corutinas provee una poderosa herramienta para esta tarea, para estos casos la caracteristica de la clave es la habilidad para voltear arriba-abajo la relacion entre llamador y llamado, esto nos da la posibilidad de poder escribir iteradores sin la preocupacion de como mantener el estado entre las sucesivas llamadas al iterador.

Anuncios

Para ilustrar el uso de esto, escribamos un iterador para atravesar todas las permutaciones del array informado, si bien no va a ser una tarea facil escribir directamente como un iterador pero tampoco es dificil escribir una funcion recursiva que permita generar estas permutaciones.

La idea es simple, pon cada elemento del array en la ultima posicion, a su vez y de forma recursiva genera todas las permutaciones de los elementos restantes, en el post anterior vimos un codigo fuente con la funcion permgen pero para que funcione correctamente deberemos crear una funcion printResult y llamar a la funcion con los argumentos apropiados, primero generaremos un codigo para guardar en un archivo:

permgen.lua

function permgen (a,n)
	n = n or #a
	if n <= 1 then
		printResult(a)
	else
		for i = 1, n do
			a[n], a[i] = a[i], a[n]
			permgen(a, n-1)
			a[n], a[i] = a[i], a[n]
		end
	end
end

function printResult(a)
	for i = 1, #a do
		io.write(a[i], " ")
	end
	io.write("\n")
end

En permgen si n no es informado tomara el valor de la cantidad de valores de a, despues si n es menor o igual a 1 simplemente muestra el valor por medio de printResult de lo contrario usara un bucle for donde pondra el valor actual del bucle (i) en el ultimo valor (n) y lo inverso, llama nuevamente a permgen pero esta vez en lugar de usar a n usa n-1 y vuelve a repetir la operacion anterior, la siguiente funcion que es printResult donde tendremos un bucle for que contara los elementos informados y lo escribira con io.write y una vez terminado escribira un salto de linea, para entender mejor este programa vamos a utilizar a dofile donde llamaremos a este archivo y despues llamaremos a la funcion permgen, veamos el ejemplo a continuacion:

Anuncios
tinchicus@dbn001dsk:~/lenguaje/lua$ lua5.3
Lua 5.3.3  Copyright (C) 1994-2016 Lua.org, PUC-Rio
> dofile("permgen.lua")
> permgen({1,2,3,4})
2 3 4 1
3 2 4 1
3 4 2 1
4 3 2 1
2 4 3 1
4 2 3 1
4 3 1 2
3 4 1 2
3 1 4 2
1 3 4 2
4 1 3 2
1 4 3 2
2 4 1 3
4 2 1 3
4 1 2 3
1 4 2 3
2 1 4 3
1 2 4 3
2 3 1 4
3 2 1 4
3 1 2 4
1 3 2 4
2 1 3 4
1 2 3 4
>

Como pueden ver hizo todas las combinaciones posibles, con nuestro generador funcionando debe ser una tarea automatica convertirla en un iterador y para ello debemos cambiar a printResult en yield:

function permgen (a,n)
	n = n or #a
	if n <= 1 then
		coroutine.yield(a) <-- Modificamos solamente esto!
	else
		for i = 1, n do
			a[n], a[i] = a[i], a[n]
			permgen(a, n-1)
			a[n], a[i] = a[i], a[n]
		end
	end
end

Nuestro siguiente paso sera definir una fabrica dentro del archivo que organice al generador para correr dentro de una corutina y luego crear la funcion del iterador:

function permutaciones(a)
        local co = coroutine.create(function() permgen(a) end)
        return function()
                local codigo, res = coroutine.resume(co)
                return res
        end
end

El iterador simplemente reanuda la corutina para producir la siguiente permutacion, el verdadero iterador es el return function()… donde reanuda la corutina creada anteriormente, con esto podriamos iterar sobre todos los elementos de un array con un simple for, veamos el siguiente ejemplo:

Anuncios
tinchicus@dbn001dsk:~/lenguaje/lua$ lua5.3
Lua 5.3.3  Copyright (C) 1994-2016 Lua.org, PUC-Rio
> dofile("permgen.lua")
> for p in permutaciones {"a", "b", "c"} do
>> printResult(p)
>> end
b c a
c b a
c a b
a c b
b a c
a b c
>

La funcion permutaciones usa un patron comun en Lua, la cual empaca una llamada para reanudar con su correspondiente corutina dentro de una funcion, como este patron es tan comun LUA nos provee una funcion especial para ello: coroutine.wrap, al igual que create, wrap crea una nueva corutina pero a diferencia de create, wrap no devuelve a la corutina en si misma en su lugar devuelve una funcion que cuando es llamado reanuda la corutina y si bien trabaja como resume, wrap no devuelve un codigo de error como su primer resultado sino en su lugar envia una notificacion siempre que haya un error, para utilizarlo deberiamos hacerlo de la siguiente forma:

function permutaciones(a)
	return coroutine.wrap(function() permgen(a) end)
end
Anuncios

Si modificamos la funcion en nuestro codigo y lo volvemos a probar deberemos obtener el mismo resultado, como habran notado coroutine.wrap es mucho mas simple que coroutine.create porque nos da exactamente lo que estamos buscando: una funcion para reanudarlo. Sin embargo es menos flexible porque no hay una forma de chequear el estado de la corutina con wrap, mas aun no podemos chequear por errores de ejecucion, veamos el codigo final de permgen.lua:

function permgen (a,n)
        n = n or #a
        if n <= 1 then
                coroutine.yield(a)
        else
                for i = 1, n do
                        a[n], a[i] = a[i], a[n]
                        permgen(a, n-1)
                        a[n], a[i] = a[i], a[n]
                end
        end
end

function printResult(a)
        for i = 1, #a do
                io.write(a[i], " ")
        end
        io.write("\n")
end

function permutaciones(a)
        return coroutine.wrap(function() permgen(a) end)
end
Anuncios

En resumen, hoy hemos visto como hacer trabajar a una corutina como iterador, hemos hecho funcionar a permgen, hemos visto como crear al iterador, primero con create, hemos visto como usar wrap, y por ultimo sus beneficios y sus contras, espero les haya sido util sigueme en Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.

Tambien podes donar

Es para mantenimiento del sitio, gracias!

$1.00