Menu Close

Combinaciones divisibles

Definir la función

   tieneCombinacionDivisible :: [Int] -> Int -> Bool

tal que (tieneCombinacionDivisible xs m) se verifica si existe alguna forma de combinar todos los elementos de la lista (con las operaciones suma o resta) de forma que el resultado sea divisible por m. Por ejemplo,

   tieneCombinacionDivisible [1,3,4,6] 4  ==  True
   tieneCombinacionDivisible [1,3,9]   2  ==  False

En el primer ejemplo, 1 – 2 + 3 + 4 + 6 = 12 es una combinación divisible por 4. En el segundo ejemplo, las combinaciones de [1,3,9] son

   1 + 3 + 9 =  13
  -1 + 3 + 9 =  11
   1 - 3 + 9 =   7
  -1 - 3 + 9 =   5
   1 + 3 - 9 =  -5
  -1 + 3 - 9 =  -7
   1 - 3 - 9 = -11
  -1 - 3 - 9 = -13

y ninguna de las 4 es divisible por 2.

Soluciones

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
tieneCombinacionDivisible :: [Int] -> Int -> Bool
tieneCombinacionDivisible xs m =
  any esDivisible (valoresCombinaciones xs)
  where esDivisible x = x `mod` m == 0
 
-- (valoresCombinaciones xs) es la lista de los valores de todas las
-- combinaciones de todos los elementos de la lista con las operaciones
-- suma o resta. Por ejemplo,
--    λ> valoresCombinaciones [1,3,4,6]
--    [14,12,8,6,6,4,0,-2,2,0,-4,-6,-6,-8,-12,-14]
--    λ> valoresCombinaciones [1,3,-4,6]
--    [6,4,0,-2,14,12,8,6,-6,-8,-12,-14,2,0,-4,-6]
valoresCombinaciones :: [Int] -> [Int]
valoresCombinaciones []     = []
valoresCombinaciones [x]    = [x,-x]
valoresCombinaciones (x:xs) = concat [[y + x, y - x] | y <- ys]
  where ys = valoresCombinaciones xs
 
-- 2ª solución
-- ===========
 
tieneCombinacionDivisible2 :: [Int] -> Int -> Bool
tieneCombinacionDivisible2 xs m =
  tieneCombinacionCongruente xs m 0
 
-- (tieneCombinacionCongruente xs m a) se verifica si existe alguna
-- forma de combinar todos los elementos de la lista xs (con las
-- operaciones suma o resta) de forma que el resultado sea congruente
-- con a módulo m. Por ejemplo,
--    tieneCombinacionCongruente [1,3,4,6] 4 0  ==  True
--    tieneCombinacionCongruente [1,3,4,6] 4 1  ==  False
--    tieneCombinacionCongruente [1,3,9] 2 0    ==  False
--    tieneCombinacionCongruente [1,3,9] 2 1    ==  True
tieneCombinacionCongruente :: [Int] -> Int -> Int -> Bool
tieneCombinacionCongruente []  _  _ = False
tieneCombinacionCongruente [x] m  a = (x - a) `mod` m == 0
tieneCombinacionCongruente (x:xs) m a =
  tieneCombinacionCongruente xs m (a-x) ||
  tieneCombinacionCongruente xs m (a+x)
 
-- Equivalencia
-- ============
 
-- La propiedad es
prop_tieneCombinacionDivisible :: [Int] -> Positive Int -> Bool
prop_tieneCombinacionDivisible xs (Positive m) =
  tieneCombinacionDivisible xs m == tieneCombinacionDivisible2 xs m
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=25}) prop_tieneCombinacionDivisible
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--    λ> (n,xs,m) = (200,[-n..n],sum [1..n]) 
--    (0.00 secs, 0 bytes)
--    λ> and [tieneCombinacionDivisible xs a | a <- [1..m]]
--    True
--    (4.74 secs, 6,536,494,976 bytes)
--    λ> and [tieneCombinacionDivisible2 xs a | a <- [1..m]]
--    True
--    (2.97 secs, 3,381,932,664 bytes)

Pensamiento

El que espera desespera,
dice la voz popular.
¡Qué verdad tan verdadera!
La verdad es lo que es,
y sigue siendo verdad
aunque se piense al revés.

Antonio Machado

5 soluciones de “Combinaciones divisibles

  1. frahidzam
    import Control.Monad (replicateM)
     
    tieneCombinacionDivisible :: [Int] -> Int -> Bool
    tieneCombinacionDivisible xs n = or [mod a n == 0 | a <- sumaCombinaciones xs]
     
    sumaCombinaciones :: [Int] -> [Int]
    sumaCombinaciones xs = [sum ys | ys <- separa 3 (zipWith (*) (concat (replicateM (length xs) [1,-1])) (cycle xs))]
     
    separa :: Int -> [Int] -> [[Int]]
    separa n [] = []
    separa n xs = (take n xs) : separa n (drop n xs)
  2. adogargon
    combina :: [Int]   -> [[Int]]
    combina [] = [[]]
    combina (x:xs) = (map (x:) (combina xs)) ++ ( map ((-x):) (combina xs))
     
    tieneCombinacionDivisible :: [Int] -> Int -> Bool
    tieneCombinacionDivisible xs k = any (==0) [ mod n k | n  <- (map sum (combina xs)) ]
  3. lucsanand
    tieneCombinacionDivisible :: [Int] -> Int -> Bool
    tieneCombinacionDivisible xs m = or [mod (sum ys) m == 0 | ys <- tDReplicate xs]
     
    tDReplicate :: [Int] -> [[Int]]
    tDReplicate xs =  nub (filter (todosDiferentes xs) zs)
     where zs = map sort (replicateM m ys)
           ys = xs ++ map (* (-1)) xs
           m = length xs
     
    todosDiferentes :: [Int] -> [Int] -> Bool
    todosDiferentes xs ys = sort (map abs xs) == sort (map abs ys)
  4. luipromor
    tieneCombinacionDivisible :: [Int] -> Int -> Bool
    tieneCombinacionDivisible xs n = any (x -> mod x n == 0) (map sum (aux xs))
      where aux [x] = [[x],[-x]]
            aux (x:xs) = map (x:) ys  ++ map (-x:) ys
              where ys = aux xs
  5. luipromor
    tieneCombinacionDivisible :: [Int] -> Int -> Bool
    tieneCombinacionDivisible xs n = any (x -> mod x n == 0) (aux xs)
      where aux [x] = [x,-x]
            aux (x:xs) = [ x + y | y <-ys]  ++ [ -x + y | y <-ys]
              where ys = aux xs

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.