Numeración de las ternas de números naturales
Las ternas de números naturales se pueden ordenar como sigue
|
1 2 3 4 5 |
(0,0,0), (0,0,1),(0,1,0),(1,0,0), (0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0), (0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),... ... |
Definir la función
|
1 |
posicion :: (Int,Int,Int) -> Int |
tal que (posicion (x,y,z)) es la posición de la terna de números naturales (x,y,z) en la ordenación anterior. Por ejemplo,
|
1 2 3 |
posicion (0,1,0) == 2 posicion (0,0,2) == 4 posicion (0,1,1) == 5 |
Comprobar con QuickCheck que
- la posición de (x,0,0) es x(x²+6x+11)/6
- la posición de (0,y,0) es y(y²+3y+ 8)/6
- la posición de (0,0,z) es z(z²+3z+ 2)/6
- la posición de (x,x,x) es x(9x²+14x+7)/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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
import Data.List (elemIndex) import Data.Maybe (fromJust) import Test.QuickCheck -- 1ª solución -- =========== posicion1 :: (Int,Int,Int) -> Int posicion1 t = aux 0 ternas where aux n (t':ts) | t' == t = n | otherwise = aux (n+1) ts -- ternas es la lista ordenada de las ternas de números naturales. Por ejemplo, -- λ> take 9 ternas -- [(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0)] ternas :: [(Int,Int,Int)] ternas = [(x,y,n-x-y) | n <- [0..], x <- [0..n], y <- [0..n-x]] -- 2ª solución -- =========== posicion2 :: (Int,Int,Int) -> Int posicion2 t = head [n | (n,t') <- zip [0..] ternas, t' == t] -- 3ª solución -- =========== posicion3 :: (Int,Int,Int) -> Int posicion3 t = indice t ternas -- (indice x ys) es el índice de x en ys. Por ejemplo, -- indice 5 [0..] == 5 indice :: Eq a => a -> [a] -> Int indice x ys = length (takeWhile (/= x) ys) -- 4ª solución -- =========== posicion4 :: (Int,Int,Int) -> Int posicion4 t = fromJust (elemIndex t ternas) -- 5ª solución -- =========== posicion5 :: (Int,Int,Int) -> Int posicion5 = fromJust . (`elemIndex` ternas) -- Equivalencia -- ============ -- La propiedad es prop_posicion_equiv :: NonNegative Int -> NonNegative Int -> NonNegative Int -> Bool prop_posicion_equiv (NonNegative x) (NonNegative y) (NonNegative z) = all (== posicion1 (x,y,z)) [f (x,y,z) | f <- [ posicion2 , posicion3 , posicion4 , posicion5 ]] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> posicion1 (147,46,116) -- 5000000 -- (5.84 secs, 2,621,428,184 bytes) -- λ> posicion2 (147,46,116) -- 5000000 -- (3.63 secs, 2,173,230,200 bytes) -- λ> posicion3 (147,46,116) -- 5000000 -- (2.48 secs, 1,453,229,880 bytes) -- λ> posicion4 (147,46,116) -- 5000000 -- (1.91 secs, 1,173,229,840 bytes) -- λ> posicion5 (147,46,116) -- 5000000 -- (1.94 secs, 1,173,229,960 bytes) -- En lo que sigue, usaremos la 5ª definición posicion :: (Int,Int,Int) -> Int posicion = posicion5 -- Propiedades -- =========== -- La 1ª propiedad es prop_posicion1 :: NonNegative Int -> Bool prop_posicion1 (NonNegative x) = posicion (x,0,0) == x * (x^2 + 6*x + 11) `div` 6 -- Su comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion1 -- +++ OK, passed 100 tests. -- La 2ª propiedad es prop_posicion2 :: NonNegative Int -> Bool prop_posicion2 (NonNegative y) = posicion (0,y,0) == y * (y^2 + 3*y + 8) `div` 6 -- Su comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion2 -- +++ OK, passed 100 tests. -- La 3ª propiedad es prop_posicion3 :: NonNegative Int -> Bool prop_posicion3 (NonNegative z) = posicion (0,0,z) == z * (z^2 + 3*z + 2) `div` 6 -- Su comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion3 -- +++ OK, passed 100 tests. -- La 4ª propiedad es prop_posicion4 :: NonNegative Int -> Bool prop_posicion4 (NonNegative x) = posicion (x,x,x) == x * (9 * x^2 + 14 * x + 7) `div` 2 -- Su comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion4 -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.
La elaboración de las soluciones se muestra en el siguiente vídeo: