Menu Close

Representación de conjuntos mediante intervalos

José A. Alonso,

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

Avanzado
, , , ,

6 soluciones de “Representación de conjuntos mediante intervalos”

  1. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.