Período de una lista
El período de una lista xs es la lista más corta ys tal que xs se puede obtener concatenando varias veces la lista ys. Por ejemplo, el período «abababab» es «ab» ya que «abababab» se obtiene repitiendo tres veces la lista «ab».
Definir la función
1 |
periodo :: Eq a => [a] -> [a] |
tal que (periodo xs) es el período de xs. Por ejemplo,
1 2 3 4 |
periodo "ababab" == "ab" periodo "buenobueno" == "bueno" periodo "oooooo" == "o" periodo "sevilla" == "sevilla" |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
import Data.List (isPrefixOf, inits) -- 1ª solución -- =========== periodo1 :: Eq a => [a] -> [a] periodo1 xs = take n xs where l = length xs n = head [m | m <- divisores l, concat (replicate (l `div` m) (take m xs)) == xs] -- (divisores n) es la lista de los divisores de n. Por ejemplo, -- divisores 96 == [1,2,3,4,6,8,12,16,24,32,48,96] divisores :: Int -> [Int] divisores n = [x | x <- [1..n], n `mod` x == 0] -- 2ª solución -- =========== periodo2 :: Eq a => [a] -> [a] periodo2 xs = take n xs where l = length xs n = head [m | m <- divisores l, xs `isPrefixOf` cycle (take m xs)] |
6 Comentarios