{"id":3645,"date":"2013-09-16T10:58:04","date_gmt":"2013-09-16T08:58:04","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3645"},"modified":"2013-09-16T10:58:04","modified_gmt":"2013-09-16T08:58:04","slug":"el-problema-de-las-sucesiones-llenas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-problema-de-las-sucesiones-llenas-en-haskell\/","title":{"rendered":"El problema de las sucesiones llenas en Haskell"},"content":{"rendered":"

En las Olimpiadas de Matem\u00e1ticas del 2002<\/a> se propuso el siguiente problema<\/p>\n

\nSea n un entero positivo. Una sucesi\u00f3n de n enteros positivos (no necesariamente distintos) se llama “llena” si verifica la siguiente condici\u00f3n: para cada entero positivo k \u2265 2, si el n\u00famero k aparece en la sucesi\u00f3n, entonces tambi\u00e9n lo hace el n\u00famero k-1 y, adem\u00e1s, la primera ocurrencia de k-1 es anterior a la \u00faltima ocurrencia de k. Para cada n, \u00bfcu\u00e1ntas sucesiones llenas existen?\n<\/p><\/blockquote>\n

En la siguiente relaci\u00f3n de ejercicios, elaborada para la asignatura de Inform\u00e1tica (de 1\u00ba del Grado en Matem\u00e1ticas)<\/a>, se estudia con Haskell el problema.
\n<\/p>\n

\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 1\u00aa soluci\u00f3n (por fuerza bruta)                                   --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n \r\n--    primera :: Eq a => a -> [a] -> Int\r\n-- tal que (primera x ys) es la posici\u00f3n de la primera\r\n-- ocurrencia de x en ys. Por ejemplo,\r\n--    primera 5 [3,2,5,7,5,4]  ==  2\r\n--    primera 9 [3,2,5,7,5,4]  ==  6\r\n-- ---------------------------------------------------------------------\r\n\r\nprimera :: Eq a => a -> [a] -> Int\r\nprimera x ys = length (takeWhile (\/=x) ys)\r\n            \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n \r\n--    ultima :: Eq a => a -> [a] -> Int\r\n-- tal que (ultima x ys) es la posici\u00f3n de la \u00faltima\r\n-- ocurrencia de x en ys. Por ejemplo,\r\n--    ultima 5 [3,2,5,7,5,4]  ==  4\r\n--    ultima 9 [3,2,5,7,5,4]  ==  -1\r\n-- ---------------------------------------------------------------------\r\n\r\nultima :: Eq a => a -> [a] -> Int\r\nultima x ys = length ys - primera x (reverse ys) - 1\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n \r\n--    esLlena :: [Int] -> Bool\r\n-- tal que (esLlena xs) se verifica si la sucesi\u00f3n xs es llena. Por\r\n-- ejemplo, \r\n--    esLlena [1,2,2,3]    ==  True\r\n--    esLlena [1,2,1,2,3]  ==  True\r\n--    esLlena [1,2,2,4]    ==  False\r\n--    esLlena [1,2,2,4,3]  ==  False\r\n--    esLlena [1,2,3,2,4]  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nesLlena :: [Int] -> Bool\r\nesLlena ns = and [cond k ns | k <- numeros ns]\r\n    where numeros   = nub . filter (>=2)\r\n          cond k ns | k `elem` ns = (k-1) `elem` ns &&\r\n                                    primera (k-1) ns < ultima k ns\r\n                    | otherwise = True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    variacionesR :: Int -> [a] -> [[a]]\r\n-- tal que (variacionesR k xs) es la lista de las variaciones de orden\r\n-- k de los elementos de xs con repeticiones. Por ejemplo,\r\n--    ghci> variacionesR 1 \"ab\"\r\n--    [\"a\",\"b\"]\r\n--    ghci> variacionesR 2 \"ab\"\r\n--    [\"aa\",\"ab\",\"ba\",\"bb\"]\r\n--    ghci> variacionesR 3 \"ab\"\r\n--    [\"aaa\",\"aab\",\"aba\",\"abb\",\"baa\",\"bab\",\"bba\",\"bbb\"]\r\n-- ---------------------------------------------------------------------\r\n\r\nvariacionesR :: Int -> [a] -> [[a]]\r\nvariacionesR _ [] = [[]]\r\nvariacionesR 0 _  = [[]] \r\nvariacionesR k xs =\r\n    [z:ys | z <- xs, ys <- variacionesR (k-1) xs]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    sucesiones :: Int -> [[Int]]\r\n-- tal que (sucesiones n) es la lista de las sucesiones de longitud n\r\n-- formada por los n primeros n\u00fameros. Por ejemplo,\r\n--    ghci> sucesiones 2\r\n--    [[1,1],[1,2],[2,1],[2,2]]\r\n--    ghci> sucesiones 3\r\n--    [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],\r\n--     [1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],\r\n--     [2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],\r\n--     [3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],\r\n--     [3,3,1],[3,3,2],[3,3,3]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesiones :: Int -> [[Int]]\r\nsucesiones n = variacionesR n [1..n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    sucesionesLlenas :: Int -> [[Int]]\r\n-- tal que (sucesionesLlenas n) es la lista de las sucesiones llenas de\r\n-- longitud n. Por ejemplo,\r\n--    ghci> sucesionesLlenas 1\r\n--    [[1]]\r\n--    ghci> sucesionesLlenas 2\r\n--    [[1,1],[1,2]]\r\n--    ghci> sucesionesLlenas 3\r\n--    [[1,1,1],[1,1,2],[1,2,1],\r\n--     [1,2,2],[1,2,3],[2,1,2]]\r\n--    ghci> sucesionesLlenas 4\r\n--    [[1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,2,2],\r\n--     [1,1,2,3],[1,2,1,1],[1,2,1,2],[1,2,1,3],\r\n--     [1,2,2,1],[1,2,2,2],[1,2,2,3],[1,2,3,1],\r\n--     [1,2,3,2],[1,2,3,3],[1,2,3,4],[1,3,2,3],\r\n--     [2,1,1,2],[2,1,2,1],[2,1,2,2],[2,1,2,3],\r\n--     [2,1,3,2],[2,2,1,2],[2,3,1,2],[3,1,2,3]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesionesLlenas :: Int -> [[Int]]\r\nsucesionesLlenas n = [xs | xs <- sucesiones n, esLlena xs]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Calcular el n\u00famero de sucesiones llenas de longitud n,\r\n-- para n entre 1 y 5. Conjeturar dicho n\u00famero para cualquier n.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    length (sucesionesLlenas 1)  ==  1\r\n--    length (sucesionesLlenas 2)  ==  2\r\n--    length (sucesionesLlenas 3)  ==  6\r\n--    length (sucesionesLlenas 4)  ==  24\r\n--    length (sucesionesLlenas 5)  ==  120\r\n\r\n-- La conjetura es que el n\u00famero de sucesiones llenas de longitud n es\r\n-- n!.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 2\u00aa soluci\u00f3n (por recursi\u00f3n)                                      --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n \r\n--    reducida :: [Int] -> [Int]\r\n-- tal que (reducida xs) es la sucesi\u00f3n obtenida eliminando en xs la\r\n-- primera ocurrencia de su mayor elemento. Por ejemplo, \r\n--    reducida [2,5,3,5]    ==  [2,3,5]\r\n--    reducida [7,2,5,3,5]  ==  [2,5,3,5]\r\n-- ---------------------------------------------------------------------\r\n\r\nreducida :: [Int] -> [Int]\r\nreducida xs = take i xs ++ drop (i+1) xs\r\n    where k = maximum xs\r\n          i = primera k xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir la funci\u00f3n\r\n--    invariante :: [Int] -> Bool\r\n-- tal que (invariante xs) se verifica si la propiedad de ser llena se\r\n-- mantiene por las reducciones; es decir, si xs es llena entonces \r\n-- (reducida xs) tambi\u00e9n lo es.\r\n-- ---------------------------------------------------------------------\r\n\r\ninvariante :: [Int] -> Bool\r\ninvariante xs | esLlena xs = esLlena (reducida xs)\r\n              | otherwise  = True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    invariantes :: Int -> Bool\r\n-- tal que (invariantes n) se verifica si para todas las sucesiones xs\r\n-- llenas de longitud n se cumple (invariante xs).\r\n-- ---------------------------------------------------------------------\r\n\r\ninvariantes :: Int -> Bool\r\ninvariantes n = all invariante (sucesionesLlenas n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Comprobar (invariantes n) para n entre 1 y 5.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> invariantes 1\r\n--    True\r\n--    ghci> invariantes 2\r\n--    True\r\n--    ghci> invariantes 3\r\n--    True\r\n--    ghci> invariantes 4\r\n--    True\r\n--    ghci> invariantes 5\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n\r\n--    expansion :: [Int] -> Int -> [Int]\r\n-- tal que (expansion xs i) es la sucesi\u00f3n llena obtenida a\u00f1adiendo un\r\n-- elemento en la posici\u00f3n i a la sucesi\u00f3n llena xs. Por ejemplo,\r\n--    ghci> [expansion [1,2,3] i | i <- [0..3]]\r\n--    [[3,1,2,3],[1,3,2,3],[1,2,3,3],[1,2,3,4]]\r\n-- ---------------------------------------------------------------------\r\n\r\nexpansion :: [Int] -> Int -> [Int]\r\nexpansion xs i\r\n    | esLlena ys = ys\r\n    | otherwise  = as ++ (k:bs) \r\n    where (as,bs) = splitAt i xs\r\n          k       = maximum xs\r\n          ys      = as ++ ((k+1):bs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n\r\n--    expansiones :: [Int] -> [[Int]]\r\n-- tal que (expansiones xs) son las listas llenas obtenidas a\u00f1adiendo un\r\n-- elemento a las sucesiones llenas xs. Por ejemplo,\r\n--    ghci> expansiones [1,1,1]\r\n--    [[1,1,1,1],[1,2,1,1],[1,1,2,1],[1,1,1,2]]\r\n--    ghci> expansiones [1,1,2]\r\n--    [[2,1,1,2],[1,2,1,2],[1,1,2,2],[1,1,2,3]]\r\n--    ghci> expansiones [1,2,1]\r\n--    [[2,1,2,1],[1,2,2,1],[1,2,3,1],[1,2,1,3]]\r\n--    ghci> expansiones [1,2,2]\r\n--    [[2,1,2,2],[1,2,2,2],[1,2,3,2],[1,2,2,3]]\r\n--    ghci> expansiones [1,2,3]\r\n--    [[3,1,2,3],[1,3,2,3],[1,2,3,3],[1,2,3,4]]\r\n--    ghci> expansiones [2,1,2]\r\n--    [[2,2,1,2],[2,3,1,2],[2,1,3,2],[2,1,2,3]]\r\n-- ---------------------------------------------------------------------\r\n\r\nexpansiones :: [Int] -> [[Int]]\r\nexpansiones xs = [expansion xs i | i <- [0..length xs]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir recursivamente la funci\u00f3n\r\n--    sucesionesLlenas2 :: Int -> [[Int]]\r\n-- tal que (sucesionesLlenas2 n) es la lista de las sucesiones llenas de\r\n-- longitud n. Por ejemplo,\r\n--    ghci> sucesionesLlenas2 1\r\n--    [[1]]\r\n--    ghci> sucesionesLlenas2 2\r\n--    [[1,1],[1,2]]\r\n--    ghci> sucesionesLlenas2 3\r\n--    [[1,1,1],[1,1,1],[1,1,2],\r\n--     [2,1,2],[1,2,2],[1,2,3]]\r\n--    ghci> sucesionesLlenas2 4\r\n--    [[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,2],\r\n--     [1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,2],\r\n--     [2,1,1,2],[1,2,1,2],[1,1,2,2],[1,1,2,3],\r\n--     [2,2,1,2],[2,2,1,2],[2,1,2,2],[2,1,2,3],\r\n--     [2,1,2,2],[1,2,2,2],[1,2,2,2],[1,2,2,3],\r\n--     [3,1,2,3],[1,3,2,3],[1,2,3,3],[1,2,3,4]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesionesLlenas2 :: Int -> [[Int]]\r\nsucesionesLlenas2 0 = [[]]\r\nsucesionesLlenas2 1 = [[1]]\r\nsucesionesLlenas2 n = \r\n    concat [expansiones xs | xs <- sucesionesLlenas2 (n-1)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Definir la funci\u00f3n\r\n--    equivalentes :: Int -> Bool\r\n-- tal que (equivalentes n) se verifica si los conjuntos \r\n-- (sucesionesLlenas n) y (sucesionesLlenas2 n) son iguales. Por\r\n-- ejemplo, \r\n--    equivalentes 3  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nequivalentes :: Int -> Bool\r\nequivalentes n =\r\n    sort (sucesionesLlenas n) == sort (sucesionesLlenas2 n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Comprobar la equivalencia de las definiciones de \r\n-- sucesionesLlenas y sucesionesLlenas2 para n entre 1 y 6.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> all equivalentes [1..6]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 3\u00aa soluci\u00f3n (mediante correspondencia con las permutaciones)     --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Definir la funci\u00f3n\r\n--    segmentosDecrecientes :: [Int] -> [[Int]]\r\n-- tal que (segmentosDecrecientes xs) es la lista de los segmentos\r\n-- decrecientes de xs. Por ejemplo,\r\n--    ghci> segmentosDecrecientes [7,4,5,3,6,2,1]\r\n--    [[7,4],[5,3],[6,2,1]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsegmentosDecrecientes :: [Int] -> [[Int]]\r\nsegmentosDecrecientes (x1:x2:xs)\r\n    | x1 > x2   = (x1:ys):yss\r\n    | otherwise = [x1]:(ys:yss)\r\n    where (ys:yss) = segmentosDecrecientes (x2:xs)\r\nsegmentosDecrecientes [x] =[[x]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 18. Definir la funci\u00f3n\r\n--    elementosConPosiciones :: [[a]] -> [(a,Int)]\r\n-- tal que (elementosConPosiciones xss) es la lista de los elementos de\r\n-- las listas de xss etiquetados con su posici\u00f3n. Por ejemplo,\r\n--    ghci> elementosConPosiciones [[7,4],[5,3],[6,2,1]]\r\n--    [(7,1),(4,1),(5,2),(3,2),(6,3),(2,3),(1,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\nelementosConPosiciones :: [[a]] -> [(a,Int)]\r\nelementosConPosiciones xss = concatMap aux (zip xss [1..])\r\n    where aux (xs,k) = [(x,k) | x <- xs]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 19. Definir la funci\u00f3n\r\n--    segundosOrdenados :: Ord a => [(a,Int)] -> [Int]\r\n-- tal que (segundosOrdenados ps) es la lista de las segundas componentes de\r\n-- los pares ps ordenada seg\u00fan las primeras componentes. Por ejemplo,\r\n--    ghci> segundosOrdenados [(7,1),(4,1),(5,2),(3,2),(6,3),(2,3),(1,3)]\r\n--    [3,3,2,1,2,3,1]\r\n-- ---------------------------------------------------------------------\r\n\r\nsegundosOrdenados :: Ord a => [(a,Int)] -> [Int]\r\nsegundosOrdenados ps = [k | (x,k) <- sort ps] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 20. A cada permutaci\u00f3n se le puede hacer corresponder una\r\n-- sucesi\u00f3n llena utilizando los ejercicios anteriores. Por ejemplo,\r\n-- dada la permutaci\u00f3n [7,4,5,3,6,2,1] se calcula sus segmentos\r\n-- decrecientes \r\n--    ghci> segmentosDecrecientes [7,4,5,3,6,2,1]\r\n--    [[7,4],[5,3],[6,2,1]]\r\n-- se etiquetan los segmentos con las posiciones   \r\n--    ghci> elementosConPosiciones [[7,4],[5,3],[6,2,1]]\r\n--    [(7,1),(4,1),(5,2),(3,2),(6,3),(2,3),(1,3)]\r\n-- y se calcula los segundos elementos ordenados por los primeros\r\n--    ghci> segundosOrdenados [(7,1),(4,1),(5,2),(3,2),(6,3),(2,3),(1,3)]\r\n--    [3,3,2,1,2,3,1]\r\n-- \r\n-- Definir la funci\u00f3n \r\n--    permutacionAllena:: [Int] -> [Int]\r\n-- tal que (permutacionAllena xs) es la sucesi\u00f3n llena obtenida a partir\r\n-- de la permutaci\u00f3n xs seg\u00fan el procedimiento anterior. Por ejemplo,\r\n--    permutacionAllena [7,4,5,3,6,2,1]  ==  [3,3,2,1,2,3,1]\r\n-- ---------------------------------------------------------------------\r\n\r\npermutacionAllena:: [Int] -> [Int]\r\npermutacionAllena =\r\n    segundosOrdenados . elementosConPosiciones . segmentosDecrecientes\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 21. Comprobar que para cualquier permutaci\u00f3n xs de los\r\n-- elementos 1,2,3,4 se tiene que (permutacionAllena xs) es una sucesi\u00f3n\r\n-- llena. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> all esLlena [permutacionAllena xs | xs <- permutations [1..4]]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 22. Definir, usando permutacionAllena, la funci\u00f3n\r\n--    sucesionesLlenas3 :: Int -> [[Int]]\r\n-- tal que (sucesionesLlenas3 n) es la lista de las sucesiones llenas de\r\n-- longitud n. Por ejemplo,\r\n--    ghci> sucesionesLlenas3 1\r\n--    [[1]]\r\n--    ghci> sucesionesLlenas3 2\r\n--    [[1,2],[1,1]]\r\n--    ghci> sucesionesLlenas3 3\r\n--    [[1,2,3],[1,1,2],[1,1,1],[2,1,2],[1,2,1],[1,2,2]]\r\n--    ghci> sucesionesLlenas3 4\r\n--    [[1,2,3,4],[1,1,2,3],[1,1,1,2],[2,1,2,3],[1,2,1,3],[1,2,2,3],\r\n--     [1,1,1,1],[2,2,1,2],[2,1,1,2],[2,1,2,1],[2,1,2,2],[3,1,2,3],\r\n--     [1,2,3,1],[1,2,3,2],[1,2,3,3],[1,1,2,1],[2,1,3,2],[1,1,2,2],\r\n--     [1,2,2,1],[1,2,2,2],[1,3,2,3],[1,2,1,1],[2,3,1,2],[1,2,1,2]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesionesLlenas3 :: Int -> [[Int]]\r\nsucesionesLlenas3 n =                 \r\n    map permutacionAllena (permutations [1..n])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 23. Definir la funci\u00f3n\r\n--    equivalentes23 :: Int -> Bool\r\n-- tal que (equivalentes23 n) se verifica si los conjuntos \r\n-- (sucesionesLlenas2 n) y (sucesionesLlenas3 n) son iguales. Por\r\n-- ejemplo, \r\n--    equivalentes23 3  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nequivalentes23 :: Int -> Bool\r\nequivalentes23 n =\r\n    sort (sucesionesLlenas2 n) == sort (sucesionesLlenas3 n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 24. Comprobar la equivalencia de las definiciones de \r\n-- sucesionesLlenas2 y sucesionesLlenas3 para n entre 1 y 6.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> all equivalentes23 [1..6]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 25. Definir la funci\u00f3n\r\n--    posiciones :: Eq a => a -> [a] -> [Int]\r\n-- tal que (posiciones y xs) es la lista de las posiciones del elemento\r\n-- y en la lista xs. Por ejemplo,\r\n--    posiciones 3 [3,3,2,1,2,3,1]  ==  [1,2,6]\r\n-- ---------------------------------------------------------------------\r\n\r\nposiciones :: Eq a => a -> [a] -> [Int]\r\nposiciones y xs = [i | (x,i) <- zip xs [1..], x == y]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 26. A cada sucesi\u00f3n llena se el puede asignar una\r\n-- permutaci\u00f3n como se muestra en el siguiente ejemplo. \r\n-- \r\n-- Dada una sucesi\u00f3n llena [3,3,2,1,2,3,1], se calculan las posiciones\r\n-- de sus elementos\r\n--    posiciones 1 [3,3,2,1,2,3,1]  ==  [4,7]\r\n--    posiciones 2 [3,3,2,1,2,3,1]  ==  [3,5]\r\n--    posiciones 3 [3,3,2,1,2,3,1]  ==  [1,2,6]\r\n-- y se concatena sus inversas:\r\n--    [7,4] ++ [5,3] ++ [6,2,1]  ==  [7,4,5,3,6,2,1]\r\n-- \r\n-- Definir la funci\u00f3n \r\n--    llenaApermutacion :: [Int] -> [Int]\r\n-- tal que (llenaApermutacion xs) es la permutaci\u00f3n llena obtenida\r\n-- aplic\u00e1ndole a la permutaci\u00f3n xs el proceso anterior. Por ejemplo,\r\n--    llenaApermutacion [3,3,2,1,2,3,1]  ==  [7,4,5,3,6,2,1]\r\n-- ---------------------------------------------------------------------\r\n\r\nllenaApermutacion :: [Int] -> [Int]\r\nllenaApermutacion xs = \r\n    concat [reverse (posiciones y xs) | y <- [1..maximum xs]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 27. Comprobar que las funciones permutacionAllena y\r\n-- llenaApermutacion son inversas para todas las permutaciones de [1..4]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> :{\r\n--    *Main| and [llenaApermutacion (permutacionAllena xs) == xs |\r\n--    *Main|      xs <- permutations [1..4]]\r\n--    *Main| :}\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 28. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    permutacionAllena2 :: [Int] -> [Int]\r\n-- tal que (permutacionAllena2 xs) es la sucesi\u00f3n llena correspondiente\r\n-- a la permutaci\u00f3n xs. Por ejemplo,\r\n--    permutacionAllena2 [7,4,5,3,6,2,1]  ==  [3,3,2,1,2,3,1]\r\n-- ---------------------------------------------------------------------\r\n\r\npermutacionAllena2 :: [Int] -> [Int]\r\npermutacionAllena2 xs = aux (tail xs) (head xs) 1 [(head xs,1)]\r\n    where aux [] _ _ ps = segundosOrdenados ps\r\n          aux (x:xs) y k ps | x < y     = aux xs x k ((x,k):ps)\r\n                            | otherwise = aux xs x (k+1) ((x,k+1):ps)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 29. Definir, usando permutacionAllena2, la funci\u00f3n\r\n--    sucesionesLlenas4 :: Int -> [[Int]]\r\n-- tal que (sucesionesLlenas4 n) es la lista de las sucesiones llenas de\r\n-- longitud n. Por ejemplo,\r\n--    ghci> sucesionesLlenas4 1\r\n--    [[1]]\r\n--    ghci> sucesionesLlenas4 2\r\n--    [[1,2],[1,1]]\r\n--    ghci> sucesionesLlenas4 3\r\n--    [[1,2,3],[1,1,2],[1,1,1],[2,1,2],[1,2,1],[1,2,2]]\r\n--    ghci> sucesionesLlenas4 4\r\n--    [[1,2,3,4],[1,1,2,3],[1,1,1,2],[2,1,2,3],[1,2,1,3],[1,2,2,3],\r\n--     [1,1,1,1],[2,2,1,2],[2,1,1,2],[2,1,2,1],[2,1,2,2],[3,1,2,3],\r\n--     [1,2,3,1],[1,2,3,2],[1,2,3,3],[1,1,2,1],[2,1,3,2],[1,1,2,2],\r\n--     [1,2,2,1],[1,2,2,2],[1,3,2,3],[1,2,1,1],[2,3,1,2],[1,2,1,2]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesionesLlenas4 :: Int -> [[Int]]\r\nsucesionesLlenas4 n =                 \r\n    map permutacionAllena2 (permutations [1..n])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 30. Definir la funci\u00f3n\r\n--    equivalentes34 :: Int -> Bool\r\n-- tal que (equivalentes23 n) se verifica si los conjuntos \r\n-- (sucesionesLlenas3 n) y (sucesionesLlenas4 n) son iguales. Por\r\n-- ejemplo, \r\n--    equivalentes34 3  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nequivalentes34 :: Int -> Bool\r\nequivalentes34 n =\r\n    sort (sucesionesLlenas3 n) == sort (sucesionesLlenas4 n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 31. Comprobar la equivalencia de las definiciones de \r\n-- sucesionesLlenas3 y sucesionesLlenas4 para n entre 1 y 6.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> all equivalentes34 [1..6]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 32. Comparar el tiempo necesario para calcular las\r\n-- sucesiones llenas de longitud n (para n igual a 7 y 10) usando las 4\r\n-- definiciones.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comparaci\u00f3n es\r\n--    ghci> :set +s\r\n--    ghci> length (sucesionesLlenas 7)\r\n--    5040\r\n--    (14.66 secs, 1576034020 bytes)\r\n--    ghci> length (sucesionesLlenas2 7)\r\n--    5040\r\n--    (0.04 secs, 3618916 bytes)\r\n--    ghci> length (sucesionesLlenas3 7)\r\n--    5040\r\n--    (0.00 secs, 1554660 bytes)\r\n--    ghci> length (sucesionesLlenas4 7)\r\n--    5040\r\n--    (0.00 secs, 1551664 bytes)\r\n--    \r\n--    ghci> length (sucesionesLlenas2 10)\r\n--    3628800\r\n--    (21.79 secs, 2532086220 bytes)\r\n--    ghci> length (sucesionesLlenas3 10)\r\n--    3628800\r\n--    (0.65 secs, 706143740 bytes)\r\n--    ghci> length (sucesionesLlenas4 10)\r\n--    3628800\r\n--    (0.64 secs, 706143760 bytes)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
En las Olimpiadas de Matem\u00e1ticas del 2002 se propuso el siguiente problema Sea n un entero positivo. Una sucesi\u00f3n de n enteros positivos (no necesariamente distintos) se llama “llena” si verifica la siguiente condici\u00f3n: para cada entero positivo k \u2265 2, si el n\u00famero k aparece en la sucesi\u00f3n, entonces tambi\u00e9n lo hace el n\u00famero…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[270,200,79],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3645"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=3645"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3645\/revisions"}],"predecessor-version":[{"id":3646,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3645\/revisions\/3646"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3645"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3645"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3645"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}