Menu Close

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

   periodo :: Eq a => [a] -> [a]

tal que (periodo xs) es el período de xs. Por ejemplo,

   periodo "ababab"      ==  "ab"
   periodo "buenobueno"  ==  "bueno"
   periodo "oooooo"      ==  "o"
   periodo "sevilla"     ==  "sevilla"

Soluciones

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 soluciones de “Período de una lista

  1. Enrique Zubiría
    periodo :: Eq a => [a] -> [a]
    periodo [] = []
    periodo xs = aux xs 1
      where aux xs l
              | xs == concat (replicate n subCadena) = subCadena
              | otherwise = aux xs (l+1)
              where subCadena = take l xs
                    n = div (length xs) (length subCadena)
  2. rebgongor
    import Data.List
    import Data.Numbers.Primes
     
    periodo :: Eq a => [a] -> [a]
    periodo [] = []
    periodo xs = take m xs
     where
       n = length xs
       ds = map (product . concat) . sequence . map inits . group . primeFactors
       m = head [x | x <- ds n, concat (replicate (div n x) (take x xs)) == xs]
  3. fercarnav
    periodo :: Eq a => [a] -> [a]
    periodo xs = periodoAux [] xs xs
     
    periodoAux _ [] zs = zs
    periodoAux xs (y:ys) zs
      | as == zs  = xs
      | otherwise = periodoAux (xs++[y]) ys zs
      where n  = length zs
            as = replica n xs
     
    replica ::Eq a => Int -> [a] -> [a]
    replica _ [] = []
    replica n xs
      | n >= x = xs ++ replica (n-x) xs
      | otherwise = take n xs
      where x = length xs
  4. javjimord
    import Data.List (inits)
     
    periodo :: Eq a => [a] -> [a]
    periodo xs =
      head [ys | ys <- tail (inits xs),
                 xs == concat (replicate ((length xs) `div` (length ys)) ys)]
  5. Enrique Zubiría
    periodo :: Eq a => [a] -> [a]
    periodo xs =
      head [ys | k <- [n | n <- [1..l],
                           rem l n == 0],
                 let ys = take k xs,
                 xs == concat (replicate (div l k) ys)]
      where l = length xs
  6. juabaerui
    periodo :: Eq a => [a] -> [a]
    periodo xs = aux xs ds
      where n = length xs
            ds = [(k,div n k) | k <- [1..n], mod n k == 0]       
            aux ys [] = ys
            aux ys ((z1,z2):zs) | ys == concat (replicate z2 t) =  t
                                | otherwise                     = aux ys zs
              where t = take z1 ys

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.