Ternas con suma acotada

2 Comentarios

1. Haskell

   import Data.List ternasAcotadas :: [Int] -> Int -> [(Int, Int, Int)] ternasAcotadas xs n = nub $ t $ concatMap (take 3) $ group $ sort xs where tails' n = takeWhile (\xs -> not (null xs) && head xs < n) . tails t xs = do (x:xs) <- tails' n xs (y:xs) <- tails' (n - x) xs (z:_ ) <- tails' (n - x - y) xs return (x, y, z) {- > ternasAcotadas [5,1,5,4,7] 12 [(1,4,5),(1,5,5)] (0.00 secs, 0 bytes) > ternasAcotadas [5,1,5,4,7] 11 [(1,4,5)] (0.00 secs, 0 bytes) > ternasAcotadas [5,1,5,4,7] 10 [] (0.00 secs, 0 bytes) > ternasAcotadas [1..10^6] 8 [(1,2,3),(1,2,4)] (0.26 secs, 130,660,488 bytes) > ternasAcotadas [10^6,10^6-1..1] 8 [(1,2,3),(1,2,4)] (0.20 secs, 89,058,336 bytes) > ternasAcotadas (take (10^6) $ cycle [5,1,5,4,7]) 12 [(1,1,1),(1,1,4),(1,1,5),(1,1,7),(1,4,4),(1,4,5),(1,5,5)] (2.71 secs, 1,508,566,128 bytes) > -}

   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

   import Data.List   ternasAcotadas :: [Int] -> Int -> [(Int, Int, Int)] ternasAcotadas xs n = nub $ t $ concatMap (take 3) $ group $ sort xs   where tails' n = takeWhile (\xs -> not (null xs) && head xs < n) . tails         t xs = do (x:xs) <- tails'  n          xs                   (y:xs) <- tails' (n - x)     xs                   (z:_ ) <- tails' (n - x - y) xs                   return (x, y, z)   {-   > ternasAcotadas [5,1,5,4,7] 12 [(1,4,5),(1,5,5)] (0.00 secs, 0 bytes) > ternasAcotadas [5,1,5,4,7] 11 [(1,4,5)] (0.00 secs, 0 bytes) > ternasAcotadas [5,1,5,4,7] 10 [] (0.00 secs, 0 bytes) > ternasAcotadas [1..10^6] 8 [(1,2,3),(1,2,4)] (0.26 secs, 130,660,488 bytes) > ternasAcotadas [10^6,10^6-1..1] 8 [(1,2,3),(1,2,4)] (0.20 secs, 89,058,336 bytes) > ternasAcotadas (take (10^6) $ cycle [5,1,5,4,7]) 12 [(1,1,1),(1,1,4),(1,1,5),(1,1,7),(1,4,4),(1,4,5),(1,5,5)] (2.71 secs, 1,508,566,128 bytes) >   -}

   Responder

2. Haskell

   ternasAcotadas :: [Int] -> Int -> [(Int,Int,Int)] ternasAcotadas xs n = nub (ternasAcotadasAux (filter (<n) (sort xs)) n) ternasAcotadasAux [] n = [] ternasAcotadasAux [_] n = [] ternasAcotadasAux zs@(x:(y:xs)) n | length zs < 3 = [] | length zs == 3 = verifica n zs | otherwise = [(x,y,z) | z <- xs, x+y+z < n] ++ ternasAcotadasAux (x:xs) n ++ ternasAcotadasAux (y:xs) n ++ ternasAcotadasAux xs n verifica n [a,b,c] | sum [a,b,c] < n = [(a,b,c)] | otherwise = []

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   ternasAcotadas :: [Int] -> Int -> [(Int,Int,Int)] ternasAcotadas xs n = nub (ternasAcotadasAux (filter (<n) (sort xs)) n)   ternasAcotadasAux [] n = [] ternasAcotadasAux [_] n = [] ternasAcotadasAux zs@(x:(y:xs)) n     | length zs < 3  = []     | length zs == 3 = verifica n zs     | otherwise      = [(x,y,z) | z <- xs, x+y+z < n] ++                        ternasAcotadasAux (x:xs) n ++                        ternasAcotadasAux (y:xs) n ++                        ternasAcotadasAux xs n   verifica n [a,b,c] | sum [a,b,c] < n = [(a,b,c)]                    | otherwise       = []

   Responder