Menu Close

Mes: mayo 2021

Ordenación de los pares de enteros

Los pares de números enteros se pueden ordenar por la suma de los valores absolutos de sus componentes. Los primeros pares en dicha ordenación son

   (0,0),
   (-1,0),(0,-1),(0,1),(1,0),
   (-2,0),(-1,-1),(-1,1),(0,-2),(0,2),(1,-1),(1,1),(2,0), ...

Definir la lista

   pares :: [(Integer, Integer)]

cuyos elementos son los pares de números enteros con la ordenación anterior. Por ejemplo,

   λ> take 38 pares
   [(0,0),(-1,0),(0,-1),(0,1),(1,0),(-2,0),(-1,-1),(-1,1),(0,-2),
    (0,2),(1,-1),(1,1),(2,0),(-3,0),(-2,-1),(-2,1),(-1,-2),(-1,2),
    (0,-3),(0,3),(1,-2),(1,2),(2,-1),(2,1),(3,0),(-4,0),(-3,-1),
    (-3,1),(-2,-2),(-2,2),(-1,-3),(-1,3),(0,-4),(0,4),(1,-3),(1,3),
    (2,-2),(2,2)]

Soluciones

import Data.List (sort)
import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
pares :: [(Integer, Integer)]
pares =
  concat [sort (concat [aux (x,n-x) | x <- [0..n]])
         | n <- [0..]]
  where
    aux (0,0) = [(0,0)]
    aux (0,y) = [(0,y), (0,-y)]
    aux (x,0) = [(x,0), (-x,0)]
    aux (x,y) = [(x,y), (-x,y), (x,-y), (-x,-y)]
 
-- 2ª solución
-- ===========
 
pares2 :: [(Integer,Integer)]
pares2 = concatMap paresEnterosSuma [0..]
 
-- (paresEnterosSuma n) es la lista de pares de enteros (x,y) tales que la suma
-- de los valores absolutos de x e y es igual a n. Por ejemplo,
--    λ> paresEnterosSuma 3
--    [(-3,0),(-2,-1),(-2,1),(-1,-2),(-1,2),(0,-3),(0,3),(1,-2),(1,2),
--     (2,-1),(2,1),(3,0)]
paresEnterosSuma :: Integer -> [(Integer,Integer)]
paresEnterosSuma n = concatMap aux [-n..n]
  where aux k | m == 0    = [(k,0)]
              | otherwise = [(k,-m),(k,m)]
          where m = n - abs k
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_pares :: Int -> Property
prop_pares n =
  n >= 0 ==>
  pares !! n == pares2 !! n
 
-- La comprobación es
--    λ> quickCheck prop_pares
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> pares !! (10^7)
--    (304,-1932)
--    (9.15 secs, 11,031,475,520 bytes)
--    λ> pares2 !! (10^7)
--    (304,-1932)
--    (2.84 secs, 3,401,450,320 bytes)

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>