Representación de conjuntos mediante intervalos

PorJosé A. Alonso 15-enero-201922-enero-2019

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

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

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

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 Comentarios

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)

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)

Responder

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

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

Responder

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

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

Responder

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)

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)

Responder

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

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

Responder

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)

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)

Responder

Representación de conjuntos mediante intervalos

Soluciones

Pensamiento

6 Comentarios

Leave a Reply to luipromorCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

6 Comentarios

Leave a Reply to luipromorCancel reply

Entradas recientes

Buscar

Correo electrónico