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
{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
sumaMaximos :: [Integer] -> Integer
tal que (sumaMaximos xs) es la suma de los máximos elementos de los subconjuntos de xs. Por ejemplo,
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
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 xs = sum (zipWith (*) (sort xs) potenciasDeDos) potenciasDeDos :: [Integer] potenciasDeDos = iterate (*2) 1 -- Comparación de eficiencia -- λ> sumaMaximos [1..20] -- 19922945 -- (3.22 secs, 720,212,384 bytes) -- λ> sumaMaximos2 [1..20] -- 19922945 -- (0.01 secs, 0 bytes)
Referencias
Basado en el artículo Sum of maximum elements of all subsets de Utkarsh Trivedi en GeeksforGeeks.