Ternas con suma acotada
Definir la función
1 |
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,
1 2 3 4 5 |
ternasAcotadas [5,1,5,4,7] 12 == [(1,4,5),(1,5,5)] ternasAcotadas [5,1,5,4,7] 11 == [(1,4,5)] ternasAcotadas [5,1,5,4,7] 10 == [] 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import Data.List (tails, sort, nub) -- 1ª definición -- ============= ternasAcotadas :: [Int] -> Int -> [(Int,Int,Int)] ternasAcotadas xs n = nub [(x,y,z) | (x,y,z) <- ternas (sort 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 = nub (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) |