Período de una lista

PorJosé A. Alonso 30-abril-20206-mayo-2020

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]

1	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"

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)]

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

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)

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)

Responder

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]

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]

Responder

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

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

Responder

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)]

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)]

Responder

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

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

Responder

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

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

Responder

Período de una lista

Soluciones

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico