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
|
1 2 3 |
(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
|
1 |
pares :: [(Integer, Integer)] |
cuyos elementos son los pares de números enteros con la ordenación anterior. Por ejemplo,
|
1 2 3 4 5 6 |
λ> 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
|
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 |
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>