El problema de la mayor subsucesión creciente en Haskell y en Clojure
A partir del problema 53 de 4Clojure, titulado Longest Increasing Sub-Seq, en el que se pide encontrar la subsucesión creciente más larga de elementos consecutivos de una sucesión dada, he elaborado dos relaciones de ejercicios. Una en Haskell, para la asignatura de Informática de 1º del Grado en Matemáticas, y la otra en Clojure, siguiendo el patrón de la anterior.
Ejercicios en Haskell
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
-- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.List (sort) import GHC.Exts (sortWith) -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- subsucesiones :: [Integer] -> [[Integer]] -- tal que (subsucesiones xs) es la lista de las subsucesiones -- crecientes de elementos consecutivos de xs. Por ejemplo, -- subsucesiones [1,0,1,2,3,0,4,5] == [[1],[0,1,2,3],[0,4,5]] -- subsucesiones [5,6,1,3,2,7] == [[5,6],[1,3],[2,7]] -- subsucesiones [2,3,3,4,5] == [[2,3],[3,4,5]] -- subsucesiones [7,6,5,4] == [[7],[6],[5],[4]] -- --------------------------------------------------------------------- subsucesiones :: [Integer] -> [[Integer]] subsucesiones [] = [] subsucesiones [x] = [[x]] subsucesiones (x:y:zs) | x < y = (x:us):vss | otherwise = [x]:p where p@(us:vss) = subsucesiones (y:zs) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- ordenadas :: [[Integer]] -> [[Integer]] -- tal que (ordenadas xss) es la lista de los elementos de xss ordenados -- de mayor a menor longitud. Por ejemplo, -- ordenadas [[1],[0,1,2,3],[0,4,5]] == [[0,1,2,3],[0,4,5],[1]] -- ordenadas [[5,6],[1,3],[2,7]] == [[5,6],[1,3],[2,7]] -- ordenadas [[2,3],[3,4,5]] == [[3,4,5],[2,3]] -- ordenadas [[7],[6],[5],[4]] == [[7],[6],[5],[4]] -- --------------------------------------------------------------------- ordenadas :: [[Integer]] -> [[Integer]] ordenadas xss = [ys | (_,_,ys) <- sort [(- length xs,n,xs) | (n,xs) <- zip [1..] xss]] -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- masLarga :: [[Integer]] -> [Integer] -- tal que (masLarga xss) es la primera lista de xss con máxima -- longitud. Por ejemplo, -- masLarga [[1],[0,1,2,3],[0,4,5]] == [0,1,2,3] -- masLarga [[5,6],[1,3],[2,7]] == [5,6] -- masLarga [[2,3],[3,4,5]] == [3,4,5] -- masLarga [[7],[6],[5],[4]] == [7] -- --------------------------------------------------------------------- masLarga :: [[Integer]] -> [Integer] masLarga = head . ordenadas -- Otra definición sin usar 'ordenada' es masLarga' xss = head [xs | xs <- xss, length xs == m] where m = maximum [length xs | xs <- xss] -- Otra definición usando 'sortWith' es masLarga'' xss = head (sortWith (\xs -> -(length xs)) xss) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- mayorSubsucesion :: [Integer] -> [Integer] -- tal que (mayorSubsucesion xss) es la primera subsucesión de elementos -- consecutivos de xss creciente y cuya longitud es máxima y es mayor o -- igual que 2. Por ejemplo, -- mayorSubsucesion [1,0,1,2,3,0,4,5] == [0,1,2,3] -- mayorSubsucesion [5,6,1,3,2,7] == [5,6] -- mayorSubsucesion [2,3,3,4,5] == [3,4,5] -- mayorSubsucesion [7,6,5,4] == [] -- --------------------------------------------------------------------- mayorSubsucesion :: [Integer] -> [Integer] mayorSubsucesion xss | length ys < 2 = [] | otherwise = ys where ys = masLarga (subsucesiones xss) |
Ejercicios en Clojure
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
;;; -------------------------------------------------------------------- ;;; Ejercicio 1. Definir la función 'subsucesiones' tal que ;;; (subsucesiones xs) es la lista de las subsucesiones crecientes de ;;; elementos consecutivos de xs. Por ejemplo, ;;; (= (subsucesiones [1 0 1 2 3 0 4 5]) [[1] [0 1 2 3] [0 4 5]]) ;;; (= (subsucesiones [5 6 1 3 2 7]) [[5 6] [1 3] [2 7]]) ;;; (= (subsucesiones [2 3 3 4 5]) [[2 3] [3 4 5]]) ;;; (= (subsucesiones [7 6 5 4]) [[7] [6] [5] [4]]) ;;; -------------------------------------------------------------------- (defn subsucesiones [xs] (cond (empty? xs) xs (= (count xs) 1) (list xs) true (let [vss (subsucesiones (rest xs))] (if (< (first xs) (second xs)) (cons (cons (first xs) (first vss)) (rest vss)) (cons (list (first xs)) vss))))) ;;; Otra definición con patrones es (defn subsucesiones [xs] (cond (= (count xs) 0) () (= (count xs) 1) (list xs) true (let [[x y & zs] xs [us & vss :as p] (subsucesiones (rest xs))] (if (< x y) (cons (cons x us) vss) (cons (list x) p))))) ;;; -------------------------------------------------------------------- ;;; Ejercicio 2. Definir la función 'ordenadas' tal que (ordenadas xss) ;;; es la lista de los elementos de xss ordenados de mayor a menor ;;; longitud. Por ejemplo, ;;; (= (ordenadas [[1] [0 1 2 3] [0 4 5]]) [[0 1 2 3] [0 4 5] [1]]) ;;; (= (ordenadas [[5 6] [1 3] [2 7]]) [[5 6] [1 3] [2 7]]) ;;; (= (ordenadas [[2 3] [3 4 5]]) [[3 4 5] [2 3]]) ;;; (= (ordenadas [[7] [6] [5] [4]]) [[7] [6] [5] [4]]) ;;; -------------------------------------------------------------------- (defn ordenadas [xss] (sort-by (fn [xs] (- (count xs))) xss)) ;;; -------------------------------------------------------------------- ;;; Ejercicio 3. Definir la función 'masLarga' tal que (masLarga xss) es ;;; la primera lista de xss con máxima longitud. Por ejemplo, ;;; (= (masLarga [[1] [0 1 2 3] [0 4 5]]) [0 1 2 3]) ;;; (= (masLarga [[5 6] [1 3] [2 7]]) [5 6]) ;;; (= (masLarga [[2 3] [3 4 5]]) [3 4 5]) ;;; (= (masLarga [[7] [6] [5] [4]]) [7]) ;;; -------------------------------------------------------------------- (defn masLarga [xs] (first (ordenadas xs))) ;;; -------------------------------------------------------------------- ;;; Ejercicio 4. Definir la función 'mayorSubsucesion' tal que ;;; (mayorSubsucesion xss) es la primera subsucesión de elementos ;;; consecutivos de xss creciente y cuya longitud es máxima y es mayor ;;; o igual que 2. Por ejemplo, ;;; (= (mayorSubsucesion [1 0 1 2 3 0 4 5]) [0 1 2 3]) ;;; (= (mayorSubsucesion [5 6 1 3 2 7]) [5 6]) ;;; (= (mayorSubsucesion [2 3 3 4 5]) [3 4 5]) ;;; (= (mayorSubsucesion [7 6 5 4]) []) ;;; -------------------------------------------------------------------- (defn mayorSubsucesion [xss] (let [ys (masLarga (subsucesiones xss))] (if (< (count ys) 2) [] ys))) |