Menu Close

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 =
  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.

Medio

5 soluciones de “Suma de los máximos de los subconjuntos

  1. josejuan
    import Data.List (sort)
     
    sumaMaximos :: [Integer] -> Integer
    sumaMaximos = sum . zipWith (p x ->x * 2^p) [0..] . sort
  2. enrnarbej
    import Data.List (sort, subsequences)
     
    -- Definición optimizada
    sumaMaximos :: [Integer] -> Integer
    sumaMaximos xs = sum $ zipWith (*) (iterate (*2) 1) (sort xs)
     
    -- Definición directa
    sumaMaximos2 :: [Integer] -> Integer
    sumaMaximos2 = sum . map maximum . tail . subsequences
  3. albcercid
    sumaMaximos :: [Integer] -> Integer
    sumaMaximos xs = operador 1 ys
      where ys                = sort xs
            operador n []     = 0
            operador n (x:xs) = n*x + operador (2*n) xs
  4. monlagare
    import Data.List (subsequences)
     
    sumaMaximos :: [Integer] -> Integer
    sumaMaximos []  = 0
    sumaMaximos [x] = x
    sumaMaximos xs  = sum (map maximum (tail (subsequences xs)))
  5. cescarde
    import Data.List (nub, sort)
     
    -- Definimos primero las funciones que vamos a usar:
    subconjuntos :: [a] -> [[a]]
    subconjuntos []     = [[]]
    subconjuntos (x:xs) = [x:y | y <- ys] ++ ys
      where ys = subconjuntos xs
     
    elsubconjunto :: [a] -> [[a]]
    elsubconjunto xs = init (subconjuntos xs)
     
    dodos :: [Integer]
    dodos = [2^(n) | n <- [0..]]
     
    -- He ido mejorando la función sumaMaximos:
     
    -- 1ª Definición:
    sumaMaximos :: [Integer] -> Integer
    sumaMaximos xs = sum [maximum x | x <- elsubconjunto xs]
     
    -- 2ª Definición:
    sumaMaximos1 :: [Integer] -> Integer
    sumaMaximos1 xs = sum (map (maximum) (elsubconjunto xs))
     
    -- 3ª Definición:
    sumaMaximos2 :: [Integer] -> Integer
    sumaMaximos2 xs =
      sum (zipWith (*) (sort (nub (map maximum (elsubconjunto xs)))) dodos)
     
    -- Tras comprobar que solamente hacía los dos primeros ejemplos, volví a
    -- intentarlo de otra forma. Observando el ejemplo inicial vi una
    -- relación entre los resultados, luego la 4ª definición es
    -- consecuencia de ello: 
    sumaMaximos3 :: [Integer] -> Integer
    sumaMaximos3 xs = sum $ zipWith (*) (dodos) (nub (sort xs))

Escribe tu solución

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