El problema 3SUM

PorJosé A. Alonso 2-enero-201819-febrero-2018

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

   sols3Sum :: [Int] -> [[Int]]
   pb3Sum :: [Int] -> Bool

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,

      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

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

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)

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)

9 Comentarios

Es una solución bastante mejorable en cuanto a la eficiencia

import Data.List

sols3Sum :: [Int] -> [[Int]]
sols3Sum xs = [y | y <- subsequences xs, length y == 3, sum y == 0]

pb3Sum :: [Int] -> Bool
pb3Sum xs |all (>0) xs || all (<0) xs = False
          |otherwise =  not (null (sols3Sum xs))

Es una solución bastante mejorable en cuanto a la eficiencia

import Data.List

sols3Sum :: [Int] -> [[Int]]

sols3Sum xs = [y | y <- subsequences xs, length y == 3, sum y == 0]

pb3Sum :: [Int] -> Bool

pb3Sum xs |all (>0) xs || all (<0) xs = False

|otherwise = not (null (sols3Sum xs))

Responder

import Data.List

sols3Sum :: [Int] -> [[Int]]
sols3Sum xs = nub $ map sort [[x,y,z] | x <- xs
                                      , y <- (xs \\ [x])
                                      , z <- (xs \\ [x,y])
                                      , sum [x,y,z] == 0]                                

pb3Sum :: [Int] -> Bool
pb3Sum = not.null.sols3Sum

import Data.List

sols3Sum :: [Int] -> [[Int]]

sols3Sum xs = nub $ map sort [[x,y,z] | x <- xs

, y <- (xs \\ [x])

, z <- (xs \\ [x,y])

, sum [x,y,z] == 0]

pb3Sum :: [Int] -> Bool

pb3Sum = not.null.sols3Sum

Responder

import Data.List (find,sort,nub,delete)
import Data.Maybe (isJust,fromJust)

sols3Sum :: [Int] -> [[Int]]
sols3Sum (x:ys@(y:z:xs)) =
  (nub
   . map sort
   . filter (not . null)
   . map (trio x ys)) ys
  ++ sols3Sum ys
sols3Sum _               = []

trio :: Int -> [Int] -> Int -> [Int]
trio x xs y | isJust fxs = [x,y,ffxs]
            | otherwise  = []
              where fxs  = find (== -x-y) $ delete y xs
                    ffxs = fromJust fxs

pb3Sum :: [Int] -> Bool
pb3Sum xs | all (< 0) xs || all (> 0) xs = False
          | otherwise                    = not . null . sols3Sum $ xs

import Data.List (find,sort,nub,delete)

import Data.Maybe (isJust,fromJust)

sols3Sum :: [Int] -> [[Int]]

sols3Sum (x:ys@(y:z:xs)) =

(nub

. map sort

. filter (not . null)

. map (trio x ys)) ys

++ sols3Sum ys

sols3Sum _ = []

trio :: Int -> [Int] -> Int -> [Int]

trio x xs y | isJust fxs = [x,y,ffxs]

| otherwise = []

where fxs = find (== -x-y) $ delete y xs

ffxs = fromJust fxs

pb3Sum :: [Int] -> Bool

pb3Sum xs | all (< 0) xs || all (> 0) xs = False

| otherwise = not . null . sols3Sum $ xs

Responder

import Data.List

sols3Sum :: [Int] -> [[Int]]
sols3Sum xs = [sort(ys) | ys <- subsequences xs,  length (ys) == 3, sum (ys) == 0]

pb3Sum :: [Int] -> Bool
pb3Sum xs |  sols3Sum xs == []    = False
          |  otherwise            = True

import Data.List

sols3Sum :: [Int] -> [[Int]]

sols3Sum xs = [sort(ys) | ys <- subsequences xs, length (ys) == 3, sum (ys) == 0]

pb3Sum :: [Int] -> Bool

pb3Sum xs | sols3Sum xs == [] = False

| otherwise = True

Responder

sols3Sum :: [Int] -> [[Int]]
sols3Sum [] = []
sols3Sum (x:xs) = sol2sum x xs ++ sols3Sum xs
  where sol2sum x xs = [[x,y,z] | (y,c) <- zip xs [1..], z <- drop c xs, y+z == (-x)]

pb3Sum :: [Int] -> Bool
pb3Sum xs | all (< 0) xs || all (> 0) xs = False
                   |  otherwise            = True

sols3Sum :: [Int] -> [[Int]]

sols3Sum [] = []

sols3Sum (x:xs) = sol2sum x xs ++ sols3Sum xs

where sol2sum x xs = [[x,y,z] | (y,c) <- zip xs [1..], z <- drop c xs, y+z == (-x)]

pb3Sum :: [Int] -> Bool

pb3Sum xs | all (< 0) xs || all (> 0) xs = False

| otherwise = True

Responder

import Data.List (sort)

sols3Sum :: [Int] -> [[Int]]
sols3Sum zs | length (filter (>0) zs) > length (filter (<0) zs) = aux (sort zs)
            | otherwise                                         = adjust (aux (sort (map (*(-1)) zs)))                    
  where aux (x:xs) | x>0       = []
                   | otherwise = (aux2 (-1*x) xs) ++ (aux xs)
          where aux2 s (a:b:cs) | a <= 0     = aux3 s a pos ++ aux2 s (b:cs)
                                | a+b <= s   = aux3 s a (b:cs) ++ aux2 s (b:cs)
                                | otherwise  = []
                  where aux3 u v (w:ws) | v+w < u   = aux3 u v ws
                                        | v+w == u  = [(-1)*u,v,w] : aux3 u v ws
                                        | otherwise = []
                        aux3 _ _ _ = [] 
                aux2 _ _ = []
                pos = filter (>=0) xs
        aux _ = []
        adjust (x:xs) = reverse (map (*(-1)) x) : adjust xs
        adjust _      = []

pb3Sum :: [Int] -> Bool
pb3Sum = not.null.sols3Sum

import Data.List (sort)

sols3Sum :: [Int] -> [[Int]]

sols3Sum zs | length (filter (>0) zs) > length (filter (<0) zs) = aux (sort zs)

| otherwise = adjust (aux (sort (map (*(-1)) zs)))

where aux (x:xs) | x>0 = []

| otherwise = (aux2 (-1*x) xs) ++ (aux xs)

where aux2 s (a:b:cs) | a <= 0 = aux3 s a pos ++ aux2 s (b:cs)

| a+b <= s = aux3 s a (b:cs) ++ aux2 s (b:cs)

| otherwise = []

where aux3 u v (w:ws) | v+w < u = aux3 u v ws

| v+w == u = [(-1)*u,v,w] : aux3 u v ws

| otherwise = []

aux3 _ _ _ = []

aux2 _ _ = []

pos = filter (>=0) xs

aux _ = []

adjust (x:xs) = reverse (map (*(-1)) x) : adjust xs

adjust _ = []

pb3Sum :: [Int] -> Bool

pb3Sum = not.null.sols3Sum

Responder

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.

import Data.List (sort)

sols3Sum :: [Int] -> [[Int]]
sols3Sum zs = sort (concat ([juntar2 a l4 | a<-l1] ++ [juntar1 a l2 | a<-l3]))
  where l1 = sort (filter (>=0) zs)
        l2 = sort (sumas l1)
        l3 = sort (map (*(-1)) (filter (<0) zs))
        l4 = sort (sumas l3)
        sumas (x:xs) = [(x+y,x,y) | y<-xs] ++ sumas xs
        sumas _ = []

juntar1 :: Int -> [(Int,Int,Int)] -> [[Int]]
juntar1 x ((a,b,c):ys) | x > a  = juntar1 x ys
                       | x == a = [(-1)*x,b,c] : juntar1 x ys
                       | x < a  = []
juntar1 _ _ = []

juntar2 :: Int -> [(Int,Int,Int)] -> [[Int]]
juntar2 x ((a,b,c):ys) | x > a  = juntar2 x ys
                       | x == a = [(-1)*c,(-1)*b,x] : juntar2 x ys
                       | x < a  = []
juntar2 _ _ = []                           
  
pb3Sum :: [Int] -> Bool
pb3Sum zs = or [aux e l4 | e<-l1] && or [aux e l2 | e<-l3]
  where l1 = sort (filter (>=0) zs)
        l2 = sort (sumas l1)
        l3 = sort (map (*(-1)) (filter (<0) zs))
        l4 = sort (sumas l3)
        sumas (x:xs) = [x+y | y<-xs] ++ sumas xs
        sumas _ = []
        aux a (b:bs) | a > b  = aux a bs
                     | a == b = True
                     | a < b  = False
        aux _ _ =  False

import Data.List (sort)

sols3Sum :: [Int] -> [[Int]]

sols3Sum zs = sort (concat ([juntar2 a l4 | a<-l1] ++ [juntar1 a l2 | a<-l3]))

where l1 = sort (filter (>=0) zs)

l2 = sort (sumas l1)

l3 = sort (map (*(-1)) (filter (<0) zs))

l4 = sort (sumas l3)

sumas (x:xs) = [(x+y,x,y) | y<-xs] ++ sumas xs

sumas _ = []

juntar1 :: Int -> [(Int,Int,Int)] -> [[Int]]

juntar1 x ((a,b,c):ys) | x > a = juntar1 x ys

| x == a = [(-1)*x,b,c] : juntar1 x ys

| x < a = []

juntar1 _ _ = []

juntar2 :: Int -> [(Int,Int,Int)] -> [[Int]]

juntar2 x ((a,b,c):ys) | x > a = juntar2 x ys

| x == a = [(-1)*c,(-1)*b,x] : juntar2 x ys

| x < a = []

juntar2 _ _ = []

pb3Sum :: [Int] -> Bool

pb3Sum zs = or [aux e l4 | e<-l1] && or [aux e l2 | e<-l3]

where l1 = sort (filter (>=0) zs)

l2 = sort (sumas l1)

l3 = sort (map (*(-1)) (filter (<0) zs))

l4 = sort (sumas l3)

sumas (x:xs) = [x+y | y<-xs] ++ sumas xs

sumas _ = []

aux a (b:bs) | a > b = aux a bs

| a == b = True

| a < b = False

aux _ _ = False

Responder

jaibengue dice:

5-enero-2018 a las 16:53

Está mal, habría que ver el número de 0s, y añadirle las combinaciones de la forma [0,0,0].

Responder

import           Data.List (nub, sort, (\\))

sols3Sum :: [Int] -> [[Int]]
sols3Sum xs = filter f zs
  where
    ms = nub . sort $ filter (<0) xs
    ps = nub . sort $ filter (>0) xs
    zs = (\x y -> [x,(-x)-y, y]) <$> ms <*> ps
    f [x,z,y] = x <= z && z <= y && z `elem` (xs\\[x,y])

pb3Sum :: [Int] -> Bool
pb3Sum = not . null . sols3Sum2

import Data.List (nub, sort, (\\))

sols3Sum :: [Int] -> [[Int]]

sols3Sum xs = filter f zs

where

ms = nub . sort $ filter (<0) xs

ps = nub . sort $ filter (>0) xs

zs = (\x y -> [x,(-x)-y, y]) <$> ms <*> ps

f [x,z,y] = x <= z && z <= y && z `elem` (xs\\[x,y])

pb3Sum :: [Int] -> Bool

pb3Sum = not . null . sols3Sum2

Responder

El problema 3SUM

Soluciones

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico