El problema 3SUM
El problem 3SUM consiste en dado una lista xs, decidir si xs posee tres elementos cuya suma sea cero. Por ejemplo, en [7,5,-9,5,2] se puede elegir los elementos 7, -9 y 2 que suman 0.
Definir las funciones
sols3Sum :: [Int] -> [[Int]] pb3Sum :: [Int] -> Bool
tales que
- (sols3Sum xs) son las listas de tres elementos de xs cuya suma sea cero. Por ejemplo,
sols3Sum [8,10,-10,-7,2,-3] == [[-10,2,8],[-7,-3,10]] sols3Sum [-2..3] == [[-2,-1,3],[-2,0,2],[-1,0,1]] sols3Sum [1,-2] == [] sols3Sum [-2,1] == [] sols3Sum [1,-2,1] == [[-2,1,1]] length (sols3Sum [-100..100]) == 5000
- (pb3Sum xs) se verifica si xs posee tres elementos cuya suma sea cero. Por ejemplo,
pb3Sum [8,10,-10,-7,2,-3] == True pb3Sum [1,-2] == False pb3Sum [-2,1] == False pb3Sum [1,-2,1] == True pb3Sum [1..400] == False
Soluciones
import Data.List -- 1ª solución -- =========== sols3Sum1 :: [Int] -> [[Int]] sols3Sum1 = normaliza . sols3Sum1Aux sols3Sum1Aux :: [Int] -> [[Int]] sols3Sum1Aux xs = [ys | ys <- subsequences xs , length ys == 3 , sum ys == 0] normaliza :: [[Int]] -> [[Int]] normaliza = sort . nub . map sort pb3Sum1 :: [Int] -> Bool pb3Sum1 = not . null . sols3Sum1Aux -- 2ª solución -- =========== sols3Sum2 :: [Int] -> [[Int]] sols3Sum2 = normaliza . sols3Sum2Aux sols3Sum2Aux :: [Int] -> [[Int]] sols3Sum2Aux xs = [[a,b,c] | (a:bs) <- tails xs , (b:cs) <- tails bs , c <- cs , a + b + c == 0] pb3Sum2 :: [Int] -> Bool pb3Sum2 = not . null . sols3Sum2Aux -- 3ª solución -- =========== sols3Sum3 :: [Int] -> [[Int]] sols3Sum3 = normaliza . sols3Sum3Aux sols3Sum3Aux :: [Int] -> [[Int]] sols3Sum3Aux xs = [[a,b,-a-b] | (a:bs) <- tails xs , b <- bs , (-a-b) `elem` (delete a (delete b xs))] pb3Sum3 :: [Int] -> Bool pb3Sum3 = not . null . sols3Sum3Aux -- Comparación de eficiencia -- ========================= -- λ> pb3Suma [1..23] -- False -- (2.61 secs, 1,812,734,176 bytes) -- λ> pb3Sumb [1..23] -- False -- (0.01 secs, 554,496 bytes) -- λ> pb3Sumc [1..23] -- False -- (0.01 secs, 584,344 bytes) -- λ> pb3Suma ([1..23] ++ [-3]) -- True -- (2.54 secs, 1,812,735,784 bytes) -- λ> pb3Sumb ([1..23] ++ [-3]) -- True -- (0.01 secs, 148,904 bytes) -- λ> pb3Sumc ([1..23] ++ [-3]) -- True -- (0.00 secs, 145,320 bytes) -- -- λ> pb3Sumb [1..300] -- False -- (1.66 secs, 933,699,824 bytes) -- λ> pb3Sumc [1..300] -- False -- (0.41 secs, 873,168,120 bytes)