aprendiendo ( Erlang ).

jueves, 5 de mayo de 2011

Listas III. Más ejemplos de listas por comprensión.

| 0 comentarios |

Como el movimiento se demuestra andando, veamos a continuación algunos ejemplos de uso de listas por comprensión.

Quicksort

De todos es conocidos el método de ordenación Quicksort. Dividimos la lista en dos: una con los menores al elemento pivote y otra con los mayores; y ambas deben estar ordenadas por lo que aplicamos nuestra función de ordenación Quicksort a cada una de ellas. Muy muy simple, elegante y claro de ver.
qsort([]) -> 
    [];
qsort([Pivot|T]) ->
    qsort([X || X <- T, X < Pivot]) ++ [Pivot | qsort([X || X <- T, X >= Pivot])].
El operador ++ concatena dos listas. Veamos pues como resulta su ejecución:
1> c(listas).
{ok,listas}
2> listas:qsort([12,2,14,1,2,3,1,1,23,45,5,6,0,3,9]).
[0,1,1,1,2,2,3,3,5,6,9,12,14,23,45]

Tripletas de Pitágoras

La tripleta de Pitagóras es un conjunto de tres enteros tal que A^2 + B^2 = C^2.
Vamos a crear una función que nos devuelva las tripletas donde la suma de sus componentes sea menor que un número dado.
tripletas_pitagoras(N) ->
    L = lists:seq(1,N),
    [{A,B,C} || A <- L, B <- L, C <- L, A+B+C =< N, A*A+B*B =:= C*C ].
Como podemos ver el ejemplo es sencillo de entender. Generamos una listas L con una secuencia de enteros desde 1 a N que nos va a servir para generar los valores de A, B y C. En la lista por comprensión encontramos tres generadores, uno para cada valor de la tripleta con valores comprendidos entre 1 y N y a continuación, las condiciones del problema. Bonito, bonito...
3> c(listas).                      
{ok,listas}
4> listas:tripletas_pitagoras(20).
[{3,4,5},{4,3,5}]

Permutaciones

Un problema complejo de resolver, en lenguajes sin un paradigma funcional, es el problemas de la generación de permutaciones. Conseguir todas las posibles combinaciones de todos los elementos de una lista puede resulta muy útil para resolver juegos matemáticos. Veamos el código.
permutaciones([]) -> 
    [[]];
permutaciones(L) -> 
    [ [H|T] || H <- L, T <- permutaciones(L--[H]) ].
Este código resulta un poco más difícil de comprender a primera vista. En este caso, tenemos dos generadores únicamente. La idea es bien simple, tomamos un elemento de la lista y permutamos el resto. Así, tenemos todas las permutaciones del primer elemento, las del segundo elemento, etc...
El operador -- realiza la diferencia entre dos listas, es decir, elimina de la primera lista los elementos de la segunda, veamos el resultado.
5> c(listas).
{ok,listas}
6> listas:permutaciones("hola").  
["hola","hoal","hloa","hlao","haol","halo","ohla","ohal",
 "olha","olah","oahl","oalh","lhoa","lhao","loha","loah",
 "laho","laoh","ahol","ahlo","aohl","aolh","alho","aloh"]

Publicar un comentario en la entrada

0 comentarios:

 
Licencia Creative Commons
Aprendiendo Erlang por Verdi se encuentra bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 3.0 Unported.