Menu Close

Menor no expresable como suma

José A. Alonso,

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>
Avanzado
, , , , , , , , ,

4 soluciones de “Menor no expresable como suma”

  1. Responder
    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. Responder
    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. Responder
    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. Responder
    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.