Menu Close

Menor no expresable como suma

Definir la función

   menorNoSuma :: [Integer] -> Integer

tal que (menorNoSuma xs) es el menor número que no se puede escribir como suma de un subconjunto de xs, donde se supone que xs es un conjunto de números enteros positivos. Por ejemplo,

   menorNoSuma [6,1,2]    ==  4
   menorNoSuma [1,2,3,9]  ==  7
   menorNoSuma [5]        ==  1
   menorNoSuma [1..20]    ==  211
   menorNoSuma [1..10^6]  ==  500000500001

Comprobar con QuickCheck que para todo n,

   menorNoSuma [1..n] == 1 + sum [1..n]

Soluciones

-- 1ª definición
-- =============
 
import Data.List (sort, subsequences)
import Test.QuickCheck
 
menorNoSuma1 :: [Integer] -> Integer
menorNoSuma1 xs =
  head [n | n <- [1..], n `notElem` sumas xs]
 
-- (sumas xs) es la lista de las sumas de los subconjuntos de xs. Por ejemplo,
--    sumas [1,2,6]  ==  [0,1,2,3,6,7,8,9]
--    sumas [6,1,2]  ==  [0,6,1,7,2,8,3,9]
sumas :: [Integer] -> [Integer]
sumas xs = map sum (subsequences xs)
 
-- 2ª definición
-- =============
 
menorNoSuma2 :: [Integer] -> Integer
menorNoSuma2  = menorNoSumaOrd . reverse . sort 
 
-- (menorNoSumaOrd xs) es el menor número que no se puede escribir como
-- suma de un subconjunto de xs, donde xs es una lista de números
-- naturales ordenada de mayor a menor. Por ejemplo,
--    menorNoSumaOrd [6,2,1]  ==  4
menorNoSumaOrd [] = 1
menorNoSumaOrd (x:xs) | x > y     = y
                      | otherwise = y+x
  where y = menorNoSumaOrd xs
 
-- Comparación de eficiencia
-- =========================
 
--    λ> menorNoSuma1 [1..20]
--    211
--    (20.40 secs, 28,268,746,320 bytes)
--    λ> menorNoSuma2 [1..20]
--    211
--    (0.01 secs, 0 bytes)
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_menorNoSuma :: (Positive Integer) -> Bool
prop_menorNoSuma (Positive n) =
  menorNoSuma2 [1..n] == 1 + sum [1..n]
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_menorNoSuma
--    +++ OK, passed 100 tests.

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

4 soluciones de “Menor no expresable como suma

  1. rebgongor

    No es eficiente para calcular el último ejemplo.

    import Test.QuickCheck
    import Data.List
     
    menorNoSuma :: [Integer] -> Integer
    menorNoSuma xs = head $ dropWhile (x -> elem x (sumas xs)) [1..]
      where sumas xs = map sum $ subsequences (sort xs)
     
    propiedad :: Positive Integer -> Bool
    propiedad (Positive n) = menorNoSuma [1..n] == 1 + sum [1..n]
     
    -- λ> quickCheckWith (stdArgs {maxSize=20}) propiedad
    -- +++ OK, passed 100 tests.
  2. Enrique Zubiría

    Mejora algo la eficiencia de la solución anterior pero no lo suficiente para el cálculo de menorNoSuma [1..10^6]

    menorNoSuma :: [Integer] -> Integer
    menorNoSuma xs = head $ filter (`notElem` sumas) [1..]
      where sumas = map sum (subconjuntos xs)
            subconjuntos []  = [[]]
            subconjuntos (x:xs) = sc ++ map (x:) sc
              where sc = subconjuntos xs
  3. javjimord
    import Data.List 
    import Test.QuickCheck
     
    menorNoSuma :: [Integer] -> Integer
    menorNoSuma xs = detecta $ (sort . nub) [sum ys | ys <- subsequences xs] 
     
    detecta :: [Integer] -> Integer
    detecta [] = 1
    detecta [x] = x + 1
    detecta (x:y:zs)
      | y /= x + 1 = x + 1
      | otherwise = detecta (y:zs)
     
    prop_MenorNoSuma :: Integer -> Property
    prop_MenorNoSuma n = n > 1 ==> menorNoSuma [1..n] == 1 + sum [1..n]
  4. fercarnav
    import Data.List (delete, nub, sort, subsequences)
    import Test.QuickCheck
     
    menorNoSuma :: [Integer] -> Integer
    menorNoSuma xs
      | a /= 0    = a
      | otherwise = m+1
      where m  = sum xs
            q  = maximum xs
            zs = faltan xs [1..q]
            a  = esNoSuma (sort xs) zs 
     
    esNoSuma :: [Integer] -> [Integer] -> Integer
    esNoSuma _ [] = 0
    esNoSuma xs (y:ys) 
      | notElem y (combinacionesSumas zs) = y
      | otherwise                         = esNoSuma xs ys
      where zs = takeWhile (< y) xs
     
    combinacionesSumas :: [Integer] -> [Integer]
    combinacionesSumas =  nub . map sum . subsequences
     
    faltan :: [Integer] -> [Integer] -> [Integer]
    faltan [] ys     = ys
    faltan _ []      = []
    faltan (x:xs) ys = faltan xs (delete x ys)
     
    prop_MenorNoSuma :: Integer -> Property
    prop_MenorNoSuma b = b /= 0 ==>
      menorNoSuma [1..n] == 1 + sum [1..n]
      where n = abs b

Escribe tu solución

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