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) |
Aquí otra definición distinta pero creo que más rápida. La idea es diferente pero creo que se puede implementar bastante mejor, si alguien lo hace por favor que lo suba.
Está mal, habría que ver el número de 0s, y añadirle las combinaciones de la forma [0,0,0].