Menu Close

Mínima diferencia de las sumas de las biparticiones de las N primeras potencias de dos

Se consideran las N primeras potencias de 2 (donde N es un número par). Por ejemplo, para N = 4, las potencias de 2 son 1, 2, 4 y 8. Las biparticiones de dichas potencias en dos conjuntos de igual tamaño son

   ([1,2],[4,8]), ([1,4],[2,8]), ([1,8],[2,4])

Las sumas de los elementos de las biparticiones son

   (3,12), (5,10), (9,6)

Los valores absolutos de las diferencias de dichas sumas son

   9, 5, 3

El mínimo de dichas diferencias es 3.

Definir la función

  minimaDiferencia :: Integer -> Integer

tal que (minimaDiferencia n) es la mínima diferencia de las sumas las biparticiones de las n (donde n es un número par) primeras potencias de dos conjuntos con igual número de elementos. Por ejemplo,

   minimaDiferencia 4  ==  3
   minimaDiferencia 6  ==  7
   minimaDiferencia (10^9) `mod` (10^9)  ==  787109375

Soluciones

import Test.QuickCheck
import Data.List ((\\))
 
-- 1ª solución
-- ===========
 
minimaDiferencia :: Integer -> Integer
minimaDiferencia n =
  minimum [abs (sum xs - sum ys) | (xs,ys) <- particiones n]
 
-- (particiones n) es la lista de las particiones de las n (donde n es
-- un número par) de las n primeras potencias de 2 en dos conjuntos de
-- igual tamaño. Por ejemplo,
--   λ> particiones 4
--   [([1,2],[4,8]),([1,4],[2,8]),([1,8],[2,4]),
--    ([2,4],[1,8]),([2,8],[1,4]),([4,8],[1,2])]
particiones :: Integer -> [([Integer],[Integer])]
particiones n =
  [(as,xs \\ as) | as <- kSubconjuntos xs (n `div` 2)]
  where xs = [2^k | k <- [0..n-1]]
 
-- (kSubconjuntos xs k) es la lista de los subconjuntos de xs con k
-- elementos. Por ejemplo,
--    λ> kSubconjuntos "bcde" 2
--    ["bc","bd","be","cd","ce","de"]
--    λ> kSubconjuntos "bcde" 3
--    ["bcd","bce","bde","cde"]
--    λ> kSubconjuntos "abcde" 3
--    ["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
kSubconjuntos :: [a] -> Integer -> [[a]]
kSubconjuntos _ 0      = [[]]
kSubconjuntos [] _     = []
kSubconjuntos (x:xs) k =
  [x:ys | ys <- kSubconjuntos xs (k-1)] ++ kSubconjuntos xs k
 
-- 2ª solución
-- ===========
 
-- Nota: La suma de las primeras (n-1) potencias de 2 es
--    sum [2^i | i <- [0..n-2]] = 2^(n-1) - 1
-- que es menor que la n-ésima potencia de 2 (es decir, 2^(n-1) porque
-- se empieza a contar en 0). Por tanto, para que la diferencia de las
-- suma sea mínima hay que agrupar la última (2^(n-1) con las menores
-- (es decir, desde 0 hasta n/2-2).
 
minimaDiferencia2 :: Integer -> Integer
minimaDiferencia2 n =
  2^(n-1) + sum [2^i | i <- [0..n `div` 2 - 2]] -
  sum [2^i | i <- [n `div` 2 - 1.. n-2]]
 
-- 3ª solución
-- ===========
 
-- Nota: Sea m = n/2 - 2. Entonces la suma de la mayor con las menores
-- es
--    s1 = 2^(n-1) + sum [2^i | i <- [0..m]]
--       = 2^(n-1) + (2^(m+1)-1)
-- y, puesto que la suma de las n primeras potencias es 2^n-1, la suma
-- de las restantes es
--    s2 = (2^n-1) - s1
 
minimaDiferencia3 :: Integer -> Integer
minimaDiferencia3 n = s1 - s2
  where m = n `div` 2 - 2
        s1 = 2^(n-1) + (2^(m+1)-1)
        s2 = (2^n-1) - s1
 
-- 4ª solución
-- ===========
 
-- Nota: Con la notación de la solución anterior, la mínima diferencia es
--    s1 - s2
--    = s1 - ((2^n-1) - s1)
--    = 2*s1 - (2^n-1)
--    = 2*(2^(n-1) + (2^(m+1)-1)) - (2^n-1)
--    = 2^n + 2^(m+2) - 2 - 2^n + 1
--    = 2^(m+2) - 1
 
minimaDiferencia4 :: Integer -> Integer
minimaDiferencia4 n = 2^(m+2) - 1
  where m = n `div` 2 - 2
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> minimaDiferencia 22
--    2047
--    (7.75 secs, 6,597,330,816 bytes)
--    λ> minimaDiferencia2 22
--    2047
--    (0.00 secs, 126,344 bytes)
--    λ> minimaDiferencia3 22
--    2047
--    (0.01 secs, 107,192 bytes)
--    λ> minimaDiferencia4 22
--    2047
--    (0.01 secs, 102,544 bytes)
--
--    λ> minimaDiferencia2 (10^5) `mod` (10^50)
--    9602443968201967760613102289456131085235835109375
--    (8.18 secs, 2,915,200,064 bytes)
--    λ> minimaDiferencia3 (10^5) `mod` (10^50)
--    9602443968201967760613102289456131085235835109375
--    (0.01 secs, 293,640 bytes)
--    λ> minimaDiferencia4 (10^5) `mod` (10^50)
--    9602443968201967760613102289456131085235835109375
--    (0.03 secs, 167,176 bytes)
--
--    λ> minimaDiferencia3 (10^8) `mod` (10^50)
--    30521751870548886367615394702753936894129787109375
--    (2.08 secs, 149,075,824 bytes)
--    λ> minimaDiferencia4 (10^8) `mod` (10^50)
--    30521751870548886367615394702753936894129787109375
--    (0.41 secs, 24,929,696 bytes)
 
-- Comprobación de equivalencia
-- ============================
 
-- Como la primera sólo calcula hasta 22, se compara la primera con la
-- cuarta para dichos valores.
prop_equivalencia1 :: Bool
prop_equivalencia1 =
  and [minimaDiferencia n == minimaDiferencia4 n | n <- [0,2..22]]
 
-- La comprobación es
--    λ> prop_equivalencia1
--    True
 
-- La propiedad de la equivalencia de las definiciones 2, 3 y 4 es
prop_equivalencia :: Integer -> Bool
prop_equivalencia n =
  all (== (minimaDiferencia2 n'))
      [minimaDiferencia3 n',
       minimaDiferencia4 n']
  where n' = 2 + abs n
 
-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

4 soluciones de “Mínima diferencia de las sumas de las biparticiones de las N primeras potencias de dos

  1. Rubén Muñoz Mkrtchian
    -- Observamos que existe un método para calcular la mínima diferencia pedida:
    --
    --   + Dada la lista [1,2,4,...,2^(n-1)] de las n primeras potencias de 2, la
    --     suma de todos los elementos de dicha lista es 1 + 2 + 4 + ... + 2^(n-1) =
    --     = 2^n - 1. Lo podemos comprobar si queremos con quickCheck.
     
    potenciasDe2 :: [Int]
    potenciasDe2 = map (2^) [0..]
     
    prop :: Int -> Property
    prop n = n > 0 ==> sum (take n potenciasDe2) == 2^n - 1
     
    -- λ> quickCheck prop
    -- +++ OK, passed 100 tests.
     
    --   + Como 2^(n-1) es mayor que la suma de todas las potencias de 2 anteriores
    --     a dicho término, tratamos de sumar a 2^(n-1) los números más pequeños que
    --     podamos. Por ejemplo, dadas las seis primeras potencias de 2, la
    --     bipartición que genera la mínima diferencia es ([1,2,32],[4,8,16]).
    --
    --   + Veamos que podemos calcular una expresión de minimaDiferencia n de
    --     forma muy sencilla. Sea m = div n 2. Las sumas de los elementos de la
    --     bipartición que genera la mínima diferencia son las siguientes:
    --       (1): 2^(n-1) + sum (take (m-1) potenciasDe2) = 2^(n-1) + 2^(m-1) - 1
    --       (2): sum (take (n-1) potenciasDe2) - sum (take (m-1) potenciasDe2) =
    --            = 2^(n-1) - 1 - (2^(m-1) - 1) = 2^(n-1) - 2^(m-1)
    --       (1-2): 2^(n-1) + 2^(m-1) - 1 - (2^(n-1) - 2^(m-1)) = 2^m - 1
     
    minimaDiferencia :: Integer -> Integer
    minimaDiferencia n = 2 ^ (div n 2) - 1
  2. Joaquín Infante Rodríguez
    import Data.List
     
    nPotenciasDeDos :: Integer -> [Integer]
    nPotenciasDeDos n = genericTake n [2^x | x<-[0..n-1]]
     
    cogeLongitudnEntre2 :: Integer -> [[Integer]] -> [[Integer]]
    cogeLongitudnEntre2 n [] = [[]]
    cogeLongitudnEntre2 0 xs = [[]]
    cogeLongitudnEntre2 n (xs:xss)
      | genericLength xs == div n 2 = (xs : cogeLongitudnEntre2 n xss)  [[]]
      | otherwise                   = cogeLongitudnEntre2 n xss
     
    biparticiones :: [[Integer]] -> [([Integer], [Integer])]
    biparticiones [[]] = [([],[])]
    biparticiones xss = [(head xss,last xss)] ++
                        biparticiones (intersect (init xss) (tail xss))
     
    pares :: [([Integer], [Integer])] -> [(Integer,Integer)]
    pares [] = []
    pares (xs:xss) = [(sum (fst xs), sum (snd xs))] ++ pares xss
     
    diferencia :: [(Integer,Integer)] -> [Integer]
    diferencia [] = []
    diferencia (x:xs) = [abs((fst x) - (snd x))] ++ diferencia xs
     
    minimaDiferenciaA1 :: Integer -> Integer
    minimaDiferenciaA1 n =  minimum
                         $ diferencia
                         $ pares
                         $ genericTake (div t 2)
                         $ biparticiones
                         $ cogeLongitudnEntre2 n
                         $ subsequences
                         $ nPotenciasDeDos n
                           where t = genericLength
                                     $ cogeLongitudnEntre2 n
                                     $ subsequences
                                     $ nPotenciasDeDos n
  3. Joaquín Infante Rodríguez
     
    import Data.List
     
    nPotenciasDeDos :: Integer -> [Integer]
    nPotenciasDeDos n = genericTake n [2^x | x<-[0..n-1]]
     
    cogeLongitudnEntre2 :: Integer -> [[Integer]] -> [[Integer]]
    cogeLongitudnEntre2 n [] = [[]]
    cogeLongitudnEntre2 0 xs = [[]]
    cogeLongitudnEntre2 n (xs:xss) | genericLength xs == div n 2 = (xs : cogeLongitudnEntre2 n xss) \\ [[]]
                                   | otherwise                   = cogeLongitudnEntre2 n xss
     
     
     
    biparticiones :: [[Integer]] -> [([Integer], [Integer])]
    biparticiones [[]] = [([],[])]
    biparticiones xss = ([(head xss,last xss)] ++ biparticiones (intersect (init xss) (tail xss)))
     
     
    pares :: [([Integer], [Integer])] -> [(Integer,Integer)]
    pares [] = []
    pares (xs:xss) = [(sum (fst xs), sum (snd xs))] ++ pares xss
     
    diferencia :: [(Integer,Integer)] -> [Integer]
    diferencia [] = []
    diferencia (x:xs) = [abs((fst x) - (snd x))] ++ diferencia xs
     
     
    minimaDiferencia :: Integer -> Integer
    minimaDiferencia n =  minimum
                        $ diferencia
                        $ pares
                        $ genericTake (div t 2)
                        $ biparticiones
                        $ cogeLongitudnEntre2 n
                        $ subsequences
                        $ nPotenciasDeDos n
                          where t = genericLength
                                    $ cogeLongitudnEntre2 n
                                    $ subsequences
                                    $ nPotenciasDeDos n
  4. Mercedes Vega Gallo
    import Data.List (subsequences,sort)
     
    minimaDiferenciaA3 :: Integer -> Integer
    minimaDiferenciaA3 n = minimum $ map q $ map p $ listas $ sublis $ pot2 n
      where p a = (sum (fst a),sum (snd a))
            q a = abs (fst a - snd a)
     
    -- La función "pot2 n" nos devuelve las N (par) primeras potencias de 2.
    pot2 :: Integer -> [Integer]
    pot2 n | even n    = take (fromIntegral n) (map (2^) [0..])
           | otherwise = error "no procede"
     
    -- La función "sublis xs" nos devuelve una lista de subconjuntos de las
    -- potencias de 2 de longitud "div (length xs) 2".
    sublis :: [Integer] -> [[Integer]]
    sublis xs = sort (filter p (subsequences xs))
      where p as = length as == div (length xs) 2
     
    -- La función "listas xss" nos devuelve una lista formada por las biparticiones
    -- de dichas potencias en dos conjuntos de igual tamaño.
    listas ::  [[Integer]] -> [([Integer],[Integer])]
    listas xss = take m (zip xss (reverse xss))
      where m = div (length xss) 2

Leave a Reply

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