Ternas con suma acotada
Definir la función
ternasAcotadas :: [Int] -> Int -> [(Int,Int,Int)]
tal que (ternasAcotadas xs n) es el conjunto de ternas de números naturales de xs cuya suma es menor que n. Por ejemplo,
ternasAcotadas [5,1,3,4,7] 12 == [(1,3,4),(1,3,5),(1,3,7),(1,4,5)] ternasAcotadas [5,1,3,4,7] 11 == [(1,3,4),(1,3,5),(1,4,5)] ternasAcotadas [5,1,3,4,7] 10 == [(1,3,4),(1,3,5)] ternasAcotadas [5,1,3,4,7] 9 == [(1,3,4)] ternasAcotadas [5,1,3,4,7] 8 == [] ternasAcotadas [1..10^6] 8 == [(1,2,3),(1,2,4)] ternasAcotadas [10^6,10^6-1..1] 8 == [(1,2,3),(1,2,4)]
Soluciones
import Data.List (tails, sort) -- 1ª definición -- ============= ternasAcotadas :: [Int] -> Int -> [(Int,Int,Int)] ternasAcotadas xs n = [(x,y,z) | (x,y,z) <- ternas xs , x+y+z < n] -- (ternas xs) es la lista de ternas de elementos de xs. Por ejemplo, -- λ> ternas [1..5] -- [(1,2,3),(1,2,4),(1,2,5),(1,3,4),(1,3,5),(1,4,5), -- (2,3,4),(2,3,5),(2,4,5), -- (3,4,5)] ternas :: [a] -> [(a,a,a)] ternas xs = [(x,y,z) | (x:ys) <- tails xs , (y:zs) <- tails ys , z <- zs] -- 2ª definición -- ============= ternasAcotadas2 :: [Int] -> Int -> [(Int,Int,Int)] ternasAcotadas2 xs n = aux (sort xs) where aux xs = [(x,y,z) | (x:ys) <- tails (takeWhile (< n) xs) , (y:zs) <- tails (takeWhile (< (n-x)) ys) , z <- (takeWhile (< (n-x-y)) zs)] -- Comparación de eficiencia -- ========================= -- λ> ternasAcotadas [1..1000] 10 -- [(1,2,3),(1,2,4),(1,2,5),(1,2,6),(1,3,4),(1,3,5),(2,3,4)] -- (336.06 secs, 50,595,444,208 bytes) -- λ> ternasAcotadas2 [1..1000] 10 -- [(1,2,3),(1,2,4),(1,2,5),(1,2,6),(1,3,4),(1,3,5),(2,3,4)] -- (0.00 secs, 0 bytes)