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 |
periodo :: Eq a => [a] -> [a] periodo 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] |
Esta solución no es válida para listas infinitas
Pero en una lista infinita no puedes saber a priori si va a tener período, ¿no?
Faltaría añadir la condición rem n (length ys) == 0, pues en casos como periodo «buenob» devuelve «bueno», que no es correcto.