Representación de conjuntos mediante intervalos

PorJosé A. Alonso 22-marzo-201725-abril-2021

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

1	intervalos [2,7,4,3,9,6] == [(2,4),(6,7),(9,9)]

Nota: Este ejercicio está basado en el problema Bus numbers de Kattis

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)

12 Comentarios

intervalos :: [Int] -> [(Int,Int)]
intervalos = concatena.separa.sort

separa [] = []
separa [x] = [(x,x)]
separa (x:y:xs) | abs (x-y) == 1 = (x,y) : separa (y:xs)
                | otherwise = (x,x) : separa (y:xs)

concatena :: [(Int,Int)] -> [(Int,Int)]
concatena [] = []
concatena [(x,y)] = [(x,y)]
concatena ((a,b):(c,d):ps) | b==c = concatena ((a,d):ps)
                           | otherwise = (a,b) : concatena ((c,d):ps)

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

intervalos = concatena.separa.sort

separa [] = []

separa [x] = [(x,x)]

separa (x:y:xs) | abs (x-y) == 1 = (x,y) : separa (y:xs)

| otherwise = (x,x) : separa (y:xs)

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

concatena [] = []

concatena [(x,y)] = [(x,y)]

concatena ((a,b):(c,d):ps) | b==c = concatena ((a,d):ps)

| otherwise = (a,b) : concatena ((c,d):ps)

Responder

intervalos :: [Int] -> [(Int,Int)]
intervalos xs = concatenar (creaInt (sort xs))


creaInt :: [Int] -> [(Int,Int)]
creaInt (x:y:xs) | abs (x-y) == 1 = (x,y):creaInt (y:xs)
                 | otherwise = creaInt (y:xs)
creaInt [x] = [(x,x)]

concatenar :: [(Int,Int)] -> [(Int,Int)]
concatenar ((x,y):(z,d):xs) | y == z = (x,d):concatenar xs
                            |otherwise = [(x,y),(z,d)] ++ concatenar xs
concatenar [] = []

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

intervalos xs = concatenar (creaInt (sort xs))

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

creaInt (x:y:xs) | abs (x-y) == 1 = (x,y):creaInt (y:xs)

| otherwise = creaInt (y:xs)

creaInt [x] = [(x,x)]

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

concatenar ((x,y):(z,d):xs) | y == z = (x,d):concatenar xs

|otherwise = [(x,y),(z,d)] ++ concatenar xs

concatenar [] = []

Responder

intervalos :: [Int] -> [(Int,Int)]
intervalos [] = []
intervalos xs = aux t (head t)
   where t = sort xs
         aux [x] a = [(a,x)]
         aux (x:y:xs) a | y <= x+1 = aux (y:xs) a
                        | otherwise = (a,x):aux (y:xs) y

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

intervalos [] = []

intervalos xs = aux t (head t)

where t = sort xs

aux [x] a = [(a,x)]

aux (x:y:xs) a | y <= x+1 = aux (y:xs) a

| otherwise = (a,x):aux (y:xs) y

Responder

import Data.List

intervalos :: [Int] -> [(Int,Int)]
intervalos [] = []
intervalos xs = aux y y z
           where z@(y:ys)       = sort xs
                 aux a b []     = [(a,b-1)]
                 aux a b r@(x:xs) | b == x    = aux a (b+1) xs
                                  | a == b    = aux (b+1) (b+1) r
                                  | otherwise = (a,b-1) : aux (b+1) (b+1) r

import Data.List

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

intervalos [] = []

intervalos xs = aux y y z

where z@(y:ys) = sort xs

aux a b [] = [(a,b-1)]

aux a b r@(x:xs) | b == x = aux a (b+1) xs

| a == b = aux (b+1) (b+1) r

| otherwise = (a,b-1) : aux (b+1) (b+1) r

Responder

intervalos = reverse . c . sort
  where c (x:xs) = foldl (\(i@(a,b):xs) c ->if c <= b+1 then (a,c):xs else (c,c):i:xs) [(x,x)] xs
        c _ = []

intervalos = reverse . c . sort

where c (x:xs) = foldl (\(i@(a,b):xs) c ->if c <= b+1 then (a,c):xs else (c,c):i:xs) [(x,x)] xs

c _ = []

Responder

intervalos = c . sort
  where c [] = []
        c [x] = [(x,x)]
        c (x:xs) = if a <= x+1 then (x,b):rs else (x,x):i:rs where i@(a,b):rs = c xs

intervalos = c . sort

where c [] = []

c [x] = [(x,x)]

c (x:xs) = if a <= x+1 then (x,b):rs else (x,x):i:rs where i@(a,b):rs = c xs

Responder

intervalos :: [Int] -> [(Int,Int)]
intervalos xs = (map head . groupBy (\a b -> snd a == snd b) . scanr aux (lsx, lsx) . zip (s:p)) p
               where
                p@(s:sx) = sort xs
                lsx = last p
                aux (a,b) (x,y) = if x-b > 1 then (a,b) else (b,y)

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

intervalos xs = (map head . groupBy (\a b -> snd a == snd b) . scanr aux (lsx, lsx) . zip (s:p)) p

where

p@(s:sx) = sort xs

lsx = last p

aux (a,b) (x,y) = if x-b > 1 then (a,b) else (b,y)

Responder

import Data.List
ordeno xs = sort xs

subconjunto [x] = [(x,x)]
subconjunto (x:y:ys) | (y - x) == 1 = (x,y) :  subconjunto (y:ys)
                     | otherwise = (x,x) : subconjunto (y:ys)


junto ((x,y):(b,c):ys) | y == b = (x,c) : junto ys
                       | otherwise = [(x,y)] ++ junto ((b,c):ys)

junto [(x,y)] = [(x,y)] 

intervalos :: [Int] -> [(Int,Int)]
intervalos xs = junto (subconjunto (ordeno xs))

import Data.List

ordeno xs = sort xs

subconjunto [x] = [(x,x)]

subconjunto (x:y:ys) | (y - x) == 1 = (x,y) : subconjunto (y:ys)

| otherwise = (x,x) : subconjunto (y:ys)

junto ((x,y):(b,c):ys) | y == b = (x,c) : junto ys

| otherwise = [(x,y)] ++ junto ((b,c):ys)

junto [(x,y)] = [(x,y)]

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

intervalos xs = junto (subconjunto (ordeno xs))

Responder

f [] = []
f [x] = [(x,x)]
f (x:y:xs) | x ==y-1 = (x,y):f (y:xs)
           | otherwise = (x,x): f(y:xs)

p [] = []
p [(x,p)] = [(x,p)]
p ((x,s):(l,m):xss)| s==l = (x,m):p xss
                   | otherwise = (x,s):p ((l,m):xss)

intervalos  xs = head(reverse(take (length xs) (iterate p (f xs))))

f [] = []

f [x] = [(x,x)]

f (x:y:xs) | x ==y-1 = (x,y):f (y:xs)

| otherwise = (x,x): f(y:xs)

p [] = []

p [(x,p)] = [(x,p)]

p ((x,s):(l,m):xss)| s==l = (x,m):p xss

| otherwise = (x,s):p ((l,m):xss)

intervalos xs = head(reverse(take (length xs) (iterate p (f xs))))

Responder

f [] = []
f [x] = [(x,x)]
f (x:y:xs) | x ==y-1 = (x,y):f (y:xs)
           | otherwise = (x,x): f(y:xs)

p [] = []
p [(x,p)] = [(x,p)]
p ((x,s):(l,m):xss)| s==l = (x,m):p xss
                   | otherwise = (x,s):p ((l,m):xss)

intervalos  xs = head(reverse(take (length xs) (iterate p (f (sort xs)))))

f [] = []

f [x] = [(x,x)]

f (x:y:xs) | x ==y-1 = (x,y):f (y:xs)

| otherwise = (x,x): f(y:xs)

p [] = []

p [(x,p)] = [(x,p)]

p ((x,s):(l,m):xss)| s==l = (x,m):p xss

| otherwise = (x,s):p ((l,m):xss)

intervalos xs = head(reverse(take (length xs) (iterate p (f (sort xs)))))

Responder

listaOrdenada :: [Int] -> [Int]
listaOrdenada [] = []
listaOrdenada [x] = [x]
listaOrdenada (x:y:xs) | x < y     = [x] ++ listaOrdenada (y:xs)
                       | otherwise = [y] ++ listaOrdenada (x:xs)

listaSeparada :: [Int] -> [(Int,Int)]
listaSeparada [] = []
listaSeparada [x] = [(x,x)]
listaSeparada (x:y:xs) | (y-x) == 1 = (x,y) : listaSeparada (y:xs)
                       | otherwise  = (x,x) : listaSeparada (y:xs)

concatena :: [(Int,Int)] -> [(Int,Int)]
concatena [] = []
concatena [(x,y)] = [(x,y)]
concatena ((z,y):(u,v):ys) | y == u    = concatena ((z,v):ys)
                           | otherwise = (z,y) : (u,v) : concatena (ys)

listaOrdenada :: [Int] -> [Int]

listaOrdenada [] = []

listaOrdenada [x] = [x]

listaOrdenada (x:y:xs) | x < y = [x] ++ listaOrdenada (y:xs)

| otherwise = [y] ++ listaOrdenada (x:xs)

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

listaSeparada [] = []

listaSeparada [x] = [(x,x)]

listaSeparada (x:y:xs) | (y-x) == 1 = (x,y) : listaSeparada (y:xs)

| otherwise = (x,x) : listaSeparada (y:xs)

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

concatena [] = []

concatena [(x,y)] = [(x,y)]

concatena ((z,y):(u,v):ys) | y == u = concatena ((z,v):ys)

| otherwise = (z,y) : (u,v) : concatena (ys)

Responder

listaOrdenada :: [Int] -> [Int]
listaOrdenada [] = []
listaOrdenada [x] = [x]
listaOrdenada (x:y:xs) | x < y     = [x] ++ listaOrdenada (y:xs)
                       | otherwise = [y] ++ listaOrdenada (x:xs)

listaSeparada :: [Int] -> [(Int,Int)]
listaSeparada [] = []
listaSeparada [x] = [(x,x)]
listaSeparada (x:y:xs) | (y-x) == 1 = (x,y) : listaSeparada (y:xs)
                       | otherwise  = (x,x) : listaSeparada (y:xs)

concatena :: [(Int,Int)] -> [(Int,Int)]
concatena [] = []
concatena [(x,y)] = [(x,y)]
concatena ((z,y):(u,v):ys) | y == u    = concatena ((z,v):ys)
                           | otherwise = (z,y) : (u,v) : concatena (ys)

intervalos :: [Int] -> [(Int,Int)]
intervalos = concatena . listaSeparada . listaOrdenada

listaOrdenada :: [Int] -> [Int]

listaOrdenada [] = []

listaOrdenada [x] = [x]

listaOrdenada (x:y:xs) | x < y = [x] ++ listaOrdenada (y:xs)

| otherwise = [y] ++ listaOrdenada (x:xs)

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

listaSeparada [] = []

listaSeparada [x] = [(x,x)]

listaSeparada (x:y:xs) | (y-x) == 1 = (x,y) : listaSeparada (y:xs)

| otherwise = (x,x) : listaSeparada (y:xs)

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

concatena [] = []

concatena [(x,y)] = [(x,y)]

concatena ((z,y):(u,v):ys) | y == u = concatena ((z,v):ys)

| otherwise = (z,y) : (u,v) : concatena (ys)

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

intervalos = concatena . listaSeparada . listaOrdenada

Responder

Representación de conjuntos mediante intervalos

Soluciones

12 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

12 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico