Problema de Ullman

José A. Alonso

06-06-2017

Definir la función

ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool

tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k elementos cuya suma sea menor que t. Por ejemplo,

ullman  9 3 [1..10]    ==  True
ullman  5 3 [1..10]    ==  False
ullman  9 5 [1..10^6]  ==  False
ullman 29 5 [1..10^6]  ==  True

Soluciones

import Data.List (sort, subsequences)

-- 1ª solución
ullman1 :: (Num a, Ord a) => a -> Int -> [a] -> Bool
ullman1 t k xs =
  (not . null) [ys | ys <- subsequences xs, length ys == k, sum ys < t]

-- 2ª solución
ullman2 :: (Ord a, Num a) => a -> Int -> [a] -> Bool
ullman2 t k xs = sum (take k (sort xs)) < t

-- Comparación de eficiencia
--    λ> ullman1 9 5 [1..23]
--    False
--    (10.73 secs, 1,761,726,376 bytes)
--    λ> ullman2 9 5 [1..23]
--    False
--    (0.01 secs, 0 bytes)