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,
|
1 |
equilibrios :: (Num a, Eq a) => [a] -> [Int] |
tal que (equilibrios xs) es la lista de las posiciones de equilibrio de xs. Por ejemplo,
|
1 2 |
equilibrios [-7,1,5,2,-4,3,0] == [3,6] equilibrios [1..10^6] == [] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
-- 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) |