Menu Close

Sustitución de pares de elementos consecutivos iguales

José A. Alonso,

Dada una lista xs se reemplaza el primer par de elementos consecutivos iguales x por x+1 y se repite el proceso con las listas obtenidas hasta que no haya ningún par de elementos consecutivos iguales. Por ejemplo, para [5,2,1,1,2,2] se tiene el siguiente proceso

       [5,2,1,1,2,2] 
   ==> [5,2,2,  2,2]
   ==> [5,3,    2,2]
   ==> [5,3,    3]
   ==> [5,4]

Definir la función

   sustitucion :: [Int] -> [Int]

tal que (sustitucion xs) es la lista obtenida aplicándole a xs el proceso anterior. Por ejemplo,

   sustitucion [5,2,1,1,2,2]         ==  [5,4]
   sustitucion [4,2,1,1,2,2]         ==  [5]
   sustitucion [4,5,11,2,5,7,2]      ==  [4,5,11,2,5,7,2]
   sustitucion (1:[1..2*10^6])       ==  [2000001]
   length (sustitucion [1..2*10^6])  ==  2000000

Soluciones

-- 1ª solución
-- ===========
 
sustitucion :: [Int] -> [Int]
sustitucion xs
  | xs == ys  = xs
  | otherwise = sustitucion ys
  where ys = sustitucionElemental xs
 
sustitucionElemental :: [Int] -> [Int]
sustitucionElemental []  = []
sustitucionElemental [x] = [x]
sustitucionElemental (x:y:zs)
  | x == y = x+1:zs
  | otherwise = x : sustitucionElemental (y:zs)
 
-- 2ª solución
-- ===========
 
sustitucion2 :: [Int] -> [Int]
sustitucion2 xs = until esPuntoFijo sustitucionElemental xs
  where esPuntoFijo ys = sustitucionElemental ys == ys
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sustitucion (1:[1..2*10^6])
--    [2000001]
--    (1.54 secs, 800,143,448 bytes)
--    λ> sustitucion2 (1:[1..2*10^6])
--    [2000001]
--    (2.21 secs, 1,072,143,584 bytes)
Posted in Inicial
Tagged , ,

2 Comments

  1. alerodrod5
    Responder 
    paso::[Int]->[Int]
paso [] = []
paso [x] = [x]
paso (x:y:xs) | x==y = (x+1):xs
              | otherwise = x:paso (y:xs)
 
sustitucion :: [Int] -> [Int]
sustitucion xs | xs==ys = xs
               |otherwise = sustitucion ys
                where ys = paso xs
  2. María Ruiz
    Responder 
     
paso :: [Int]->[Int]
paso (x:y:xs) | x==y = (x+1):xs
              | otherwise = x:paso (y:xs)
paso xs = xs              
 
sustitucion :: [Int] -> [Int]
sustitucion xs = until test paso xs
  where test xs = paso xs == xs

Escribe tu solución

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