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 pueden elegir los elementos 7, -9 y 2 que suman 0.
Definir las funciones
|
1 2 |
sols3Sum :: [Int] -> [[Int]] pb3Sum :: [Int] -> Bool |
tales que
+ (sols3Sum xs) son las listas de tres elementos de xs cuya suma sea cero. Por ejemplo,
|
1 2 3 4 5 6 |
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,
|
1 2 3 4 5 |
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
|
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
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) |