Menu Close

Representación de conjuntos mediante intervalos

Un conjunto de números enteros se pueden representar mediante una lista ordenada de intervalos tales que la diferencia entre el menor elemento de un intervalo y el mayor elemento de su intervalo anterior es mayor que uno.

Por ejemplo, el conjunto {2, 7, 4, 3, 9, 6} se puede representar mediante la lista de intervalos [(2,4),(6,7),(9,9)] de forma que en el primer intervalo se agrupan los números 2, 3 y 4; en el segundo, los números 6 y 7 y el tercero, el número 9.

Definir la función

   intervalos :: [Int] -> [(Int,Int)]

tal que (intervalos xs) es lista ordenada de intervalos que representa
al conjunto xs. Por ejemplo,

   λ> intervalos [2,7,4,3,9,6]
   [(2,4),(6,7),(9,9)]
   λ> intervalos [180,141,174,143,142,175]
   [(141,143),(174,175),(180,180)]

Soluciones

import Data.List (sort)
 
intervalos :: [Int] -> [(Int,Int)]
intervalos = map intervalo . segmentos
 
-- (segmentos xs) es la lista de segmentos formados por elementos
-- consecutivos de xs. Por ejemplo,
--    segmentos [2,7,4,3,9,6]  ==  [[2,3,4],[6,7],[9]]
segmentos :: [Int] -> [[Int]]
segmentos xs = aux as [[a]]
  where aux [] zs = zs
        aux (y:ys) ((a:as):zs) | y == a-1  = aux ys ((y:a:as):zs)
                               | otherwise = aux ys ([y]:(a:as):zs)
        (a:as) = reverse (sort xs)
 
-- (intervalo xs) es el intervalo correspondiente al segmento xs. Por
-- ejemplo, 
--    intervalo [2,3,4]  ==  (2,4)
--    intervalo [6,7]    ==  (6,7)
--    intervalo [9]      ==  (9,9)
intervalo :: [Int] -> (Int,Int)
intervalo xs = (head xs, last xs)

Pensamiento

Cuando el saber se especializa, crece el volumen total de la cultura. Esta es la ilusión y el consuelo de los especialistas. ¡Lo que sabemos entre todos! ¡Oh, eso es lo que no sabe nadie!

Antonio Machado

6 soluciones de “Representación de conjuntos mediante intervalos

  1. frahidzam
    intervalos :: [Int] -> [(Int,Int)]
    intervalos xs = map intervalo (trozo xs)
     
    trozo :: [Int] -> [[Int]]
    trozo xs = trozoAux ts [[t]]
     where trozoAux [] zs = zs
           trozoAux (y:ys) ((t:ts):zs) | y == t-1  = trozoAux ys ((y:t:ts):zs)
                                        | otherwise = trozoAux ys ([y]:(t:ts):zs)
           (t:ts) = reverse (sort xs)
     
     
    intervalo :: [Int] -> (Int, Int)
    intervalo xs = (head xs, last xs)
  2. adogargon
    import Data.List
    intervalos :: [Int] -> [(Int,Int)]
    intervalos xs = enpar (alista(sort xs))
     
    anterior :: Int -> Int -> Bool
    anterior x y = x+1 == y
     
    prop :: [Int] -> Bool
    prop (x:y:xs) = anterior x y && prop (y:xs)
    prop _ = True
     
    alista :: [Int] -> [[Int]]
    alista [] = [[]]
    alista xs =takeWhile (/=[]) ([coge xs]++alista (deja xs))
     
    enpar :: [[Int]] -> [(Int,Int)]
    enpar [] = []
    enpar (xs:xss) = ( head xs , last xs) : enpar xss
     
    coge :: [Int] -> [Int]
    coge [] = []
    coge [x] = [x]
    coge (x:y:xs) | prop (x:y:xs) = (x:y:xs)
                  | otherwise = coge (init ( x:y:xs))
     
    deja :: [Int] -> [Int]
    deja [] = [] 
    deja [x] = []
    deja (x:y:xs) | prop (x:y:xs) = []
                  | otherwise =  deja (init (x:y:xs)) ++ [last (x:y:xs)]
  3. luipromor
    intervalos :: [Int] -> [(Int,Int)]
    intervalos [] = []
    intervalos [x]= [(x,x)]
    intervalos  xs = aux ((tail.adyacentes.sort) xs) ((head.adyacentes.sort) xs)
      where adyacentes xs = zip xs (tail xs)
            aux [] (a,b) = [(a,b)]
            aux ((a,b):xs) (c,d) | b - a  > 1 && (not.null) xs = (c,a) : aux (tail xs) (head xs)
                                 | b -a > 1 = (c,d): [(b,b)]
                                 | a - d < 1 && (not.null) xs =  aux xs (c,b)
                                 | a-d < 1 &&  null xs =  [(c,b)]
  4. javmarcha1
    import Data.List
     
    intervalos :: [Int] ->[(Int,Int)]
    intervalos xs = sort (intervalosseguidos xs ++ intervalosunicos xs)
     
    intervalosunicos :: [Int] ->[(Int,Int)]
    intervalosunicos xs = [ (x,x) | x <- sacarunicos xs]
     
    intervalosseguidos :: [Int] ->[(Int,Int)]
    intervalosseguidos xs = [ (a,b) | (a,c) <- zip (sacarseguidos xs) [1..] ,
                      (b,d) <- zip (sacarseguidos xs) [1..], c==(d-1),
                      elem [a,b] (intervalosaux xs)]
     
    intervalosaux :: [Int] -> [[Int]]               
    intervalosaux xs = init (agrupaR 2 (sacarseguidos xs))
     
    sacarseguidos :: [Int] -> [Int]
    sacarseguidos xs = [ x | x <- (sort xs) ,((elem (x+1) xs) && (elem (x-1) xs == False))
                   || ((elem (x+1) xs== False) && (elem (x-1) xs))]
     
    sacarunicos :: [Int ] -> [Int ]
    sacarunicos xs = [ x | x <- (sort xs) , ((elem (x+1) xs == False)
                && (elem (x-1) xs ==False)) ]
     
    agrupaR :: Int -> [Int ] -> [[Int ]]
    agrupaR _ []                 = [[]]
    agrupaR n xs | n > length xs = [[]]
                 | otherwise = (take n xs) : agrupaR n (drop n xs)
  5. lucsanand
    import Data.List
     
    intervalos :: [Int] -> [(Int,Int)]
    intervalos ys = sort ((paresSeguidos.listaSeguidos) xs ++ (paresNoSeguidos.listaNoSeguidos)xs)
     where xs = sort ys
     
    noSeguidos :: Int ->[Int] -> Bool
    noSeguidos x xs = notElem (x+1) xs && notElem (x-1) xs
     
    seguidos :: Int -> [Int]-> Bool
    seguidos x xs =  elem (x+1) xs && elem (x-1) xs 
     
    listaNoSeguidos :: [Int]->[Int]
    listaNoSeguidos xs = [x | x<-xs, noSeguidos x xs]
     
    listaSeguidos :: [Int]->[Int]
    listaSeguidos xs = [x | x<-xs, seguidos x xs ==False, noSeguidos x xs == False]
     
    paresSeguidos :: [Int] -> [(Int,Int)]
    paresSeguidos [] = []
    paresSeguidos (x:y:xs) = (x,y):paresSeguidos xs
     
    paresNoSeguidos :: [Int]-> [(Int,Int)]
    paresNoSeguidos []=[]
    paresNoSeguidos (x:xs) = (x,x):paresNoSeguidos xs
  6. berarcmat
    intervalos :: [Int] -> [(Int,Int)]
    intervalos = pares. une. reverse. agrupa
     
    pares :: [[Int]] -> [(Int,Int)]
    pares xss = [(head xs, last xs) | xs <- xss]
     
    agrupa :: [Int] -> [[Int]]
    agrupa xs = aux (sort xs) []
      where
        aux [] zss = zss
        aux [x] zss = [x]:zss
        aux (x:y:ys) zss | x +1 >= y   = aux (y:ys) ([x,y]:zss)
                            | otherwise  = aux (y:ys) zss
     
    une :: [[Int]] -> [[Int]]
    une [] = []
    une [xs] = [xs]
    une (xs:ys:xss) | last xs == head ys    = une ((nub (xs ++ ys)):xss)
                           | otherwise       = xs:une (ys:xss)

Escribe tu solución

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