Menu Close

Posiciones de equilibrio

José A. Alonso,

Se dice que k es una posición de equilibrio de una lista xs si la suma de los elementos de xs en las posiciones menores que k es igual a la suma de los elementos de xs en las posiciones mayores que k. Por ejemplo, en la lista [-7,1,5,2,-4,3,0] el 3 es una posición de equilibrio ya que -7+1+5 = -4+3+0; también lo es el 6 ya que -7+1+5+2+(-4)+3 = 0.

Definir la función,

   equilibrios :: (Num a, Eq a) => [a] -> [Int]

tal que (equilibrios xs) es la lista de las posiciones de equilibrio de xs. Por ejemplo,

   equilibrios [-7,1,5,2,-4,3,0]  ==  [3,6]
   equilibrios [1..10^6]          ==  []

Soluciones

-- 1ª definición
-- =============
 
equilibrios1 :: (Num a, Eq a) => [a] -> [Int]
equilibrios1 xs =
  [n | n <- [0..length xs - 1]
     , sum (take n xs) == sum (drop (n+1) xs)]
 
-- 2ª definición
-- =============
 
equilibrios2 :: (Num a, Eq a) => [a] -> [Int]
equilibrios2 xs =
  [n | (n,x,y) <- zip3 [0..] (sumasI xs) (sumasD xs)
     , x == y]
 
sumasI :: (Num a, Eq a) => [a] -> [a]
sumasI xs = [sum (take n xs) | n <- [0..length xs - 1]] 
 
sumasD :: (Num a, Eq a) => [a] -> [a]
sumasD xs = [sum (drop (n+1) xs) | n <- [0..length xs - 1]] 
 
-- 3ª definición
-- =============
 
equilibrios3 :: (Num a, Eq a) => [a] -> [Int]
equilibrios3 xs =
  [n | (n,x,y) <- zip3 [0..] (sumasI' xs) (sumasD' xs)
     , x == y]
 
sumasI' :: (Num a, Eq a) => [a] -> [a]
sumasI'  = init . scanl (+) 0 
 
sumasD' :: (Num a, Eq a) => [a] -> [a]
sumasD' = tail . scanr (+) 0
 
-- 4ª definición
-- =============
 
equilibrios4 :: (Num a, Eq a) => [a] -> [Int]
equilibrios4 xs =
  [n | (n,x,y) <- zip3 [0..] (scanl1 (+) xs) (scanr1 (+) xs)
     , x == y]
 
-- Comparación de eficiencia
--    λ> let xs = [1..10^4] in equilibrios1 (xs ++ [5] ++ reverse xs)
--    [10000]
--    (20.92 secs, 46,240,541,256 bytes)
--    λ> let xs = [1..10^4] in equilibrios2 (xs ++ [5] ++ reverse xs)
--    [10000]
--    (21.12 secs, 46,249,562,520 bytes)
--    λ> let xs = [1..10^4] in equilibrios3 (xs ++ [5] ++ reverse xs)
--    [10000]
--    (0.02 secs, 11,858,768 bytes)
--    λ> let xs = [1..10^4] in equilibrios4 (xs ++ [5] ++ reverse xs)
--    [10000]
--    (0.02 secs, 13,963,952 bytes)
Posted in Avanzado
Tagged , , , , , , , , , ,

8 Comments

  1. Cescarde
    Responder 
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
equilibrios [] = []
equilibrios xs = [i-1 | (x,i) <- zip xs [1..], sumaParticiones i xs]
  where sumaParticiones i [] = False
        sumaParticiones 0 xs = False
        sumaParticiones i xs =
          sum (init (fst (splitAt i xs))) == sum (snd (splitAt i xs))
  2. paumacpar
    Responder

    equilibrios :: [Int] -> [Int]
    equilibrios xs = [ t | ((n,v),t) [(Int,Int)]
    sumas xs = zip (sumasIzquierdas xs) (sumasDerechas xs)

    sumasIzquierdas :: [Int] -> [Int]
    sumasIzquierdas xs = map sum (map fst (divisiones xs ++ [(init xs, [])]))

    sumasDerechas :: [Int] -> [Int]
    sumasDerechas xs = map sum (map snd (divisiones xs ++ [(init xs, [])]))

    divisiones :: [Int] -> [([Int],[Int])]
    divisiones [] = []
    divisiones [_] = []
    divisiones (x:xs) = ([],xs) : [(x: is,ds) | (is,ds) <- divisiones xs]

  3. enrnarbej
    Responder 
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
equilibrios xs = aux 0 0 (sum xs) xs
  where
    aux _ _ _ [] = []
    aux p si sd (x:xs)
      | si == sd - x = p : aux (p + 1) (si + x) (sd - x) xs
      | otherwise    =     aux (p + 1) (si + x) (sd - x) xs
  4. albcercid
    Responder 
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
equilibrios [] = []
equilibrios (x:xs) = auxEq 0 (sum xs) 0 (x:xs)
  where auxEq a b c [x] | a == b = [c]
                        | otherwise = []
        auxEq a b c (x:y:xs)
          | a == b    = c : auxEq (a+x) (b-y) (c+1) (y:xs)
          | otherwise =     auxEq (a+x) (b-y) (c+1) (y:xs)
  5. josejuan
    Responder 
    equilibrios xs = [i | (i, a, b) <- zip3 [0..] (scanl1 (+) xs) (scanr1 (+) xs), a == b]
  6. Juanjo Ortega (juaorture)
    Responder 
     
equilibrios :: (Num a, Eq a) => [a] -> [Int]
equilibrios xs = [x | a <- xs, let x = posicion a xs
                   , sum [xs!!b | b <- [0..x]] == sum [xs!!c | c <- [x..length xs - 1]]]
 
posicion :: Eq a => a -> [a] -> Int
posicion a (x:xs) | not ( a `elem` (x:xs)) = undefined
                  | a == x = 0
                  | otherwise = 1 + posicion a xs
 
eMonotona :: Ord a => [a] -> Bool
eMonotona (x:y:xs) = eCreciente xs || eDecreciente xs
 
eCreciente :: Ord a => [a] -> Bool
eCreciente (x:y:xs) = x < y && eCreciente (y:xs)
eCreciente _        = True
 
eDecreciente :: Ord a => [a] -> Bool
eDecreciente (x:y:xs) = x > y && eDecreciente (y:xs)
eDecreciente _        = True
 
equilibrios' :: (Ord a, Eq a, Num a) => [a] -> [Int]
equilibrios' xs | eMonotona xs = []
                | otherwise    = equilibrios xs
  7. Pablo Rabán
    Responder 
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
equilibrios [] = []
equilibrios xs =
  [n | n <- [1..(length xs - 1)] 
     , sum (take n xs) == sum (drop (n+1) xs)]
 
-- Inspirándome en la definición de juaorture, completo mi primera definición
-- añadiendo el concepto de monotonía, que mejora el rendimiento notablemente.
 
equilibrios2 :: (Ord a, Num a, Eq a) => [a] -> [Int]
equilibrios2 [] = []
equilibrios2 xs
  | creciente xs || decreciente xs = []
  | otherwise                      = equilibrios xs
 
creciente :: Ord a => [a] -> Bool
creciente (x:y:xs) = x < y && creciente (y:xs)
creciente _        = True
 
decreciente :: Ord a => [a] -> Bool
decreciente (x:y:xs) = x > y && decreciente (y:xs)
decreciente _        = True
  8. Chema Cortés
    Responder 
    equilibrios :: (Num a, Eq a) => [a] -> [Int]
equilibrios []     = []
equilibrios (x:xs) = [ i | (izq,der,i) <- zip3 izqs ders [0..]
                         , izq == der ]
    where izqs = scanl (+) 0 (x:xs)
          ders = scanl (-) (sum xs) xs

Escribe tu solución

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