Suma de los máximos de los subconjuntos
Los subconjuntos distinto del vacío del conjunto {3, 2, 5}, junto con sus máximos elementos, son
1 2 3 4 5 6 7 |
{3} su máximo es 3 {2} su máximo es 2 {5} su máximo es 5 {3, 2} su máximo es 3 {3, 5} su máximo es 5 {2, 5} su máximo es 5 {3, 2, 5} su máximo es 5 |
Por tanto, la suma de los máximos elementos de los subconjuntos de {3, 2, 5} es 3 + 2 + 5 + 3 + 5 + 5 + 5 = 28.
Definir la función
1 |
sumaMaximos :: [Integer] -> Integer |
tal que (sumaMaximos xs) es la suma de los máximos elementos de los subconjuntos de xs. Por ejemplo,
1 2 3 4 5 |
sumaMaximos [3,2,5] == 28 sumaMaximos [4,1,6,3] == 71 sumaMaximos [1..100] == 125497409422594710748173617332225 length (show (sumaMaximos [1..10^5])) == 30108 sumaMaximos [1..10^5] `mod` (10^7) == 4490625 |
Soluciones
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 |
import Data.List (sort, subsequences) -- 1ª definición sumaMaximos :: [Integer] -> Integer sumaMaximos xs = sum [maximum ys | ys <- tail (subsequences xs)] -- 2ª definición sumaMaximos2 :: [Integer] -> Integer sumaMaximos2 = sum . map maximum . tail . subsequences -- 3ª definición sumaMaximos3 :: [Integer] -> Integer sumaMaximos3 xs = sum (zipWith (*) (sort xs) potenciasDeDos) potenciasDeDos :: [Integer] potenciasDeDos = iterate (*2) 1 -- Comparación de eficiencia -- λ> sumaMaximos [1..20] -- 19922945 -- (2.74 secs, 703,957,848 bytes) -- λ> sumaMaximos2 [1..20] -- 19922945 -- (2.06 secs, 680,728,696 bytes) -- λ> sumaMaximos3 [1..20] -- 19922945 -- (0.01 secs, 0 bytes) |
Basado en el artículo
Sum of maximum elements of all subsets
de Utkarsh Trivedi en GeeksforGeeks.
5 Comentarios