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
1. Soluciones en Haskell
|
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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
import Data.List (elemIndex) import Data.Maybe (fromJust) import Test.Hspec (Spec, describe, hspec, it, shouldBe) 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) -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: ((Int,Int,Int) -> Int) -> Spec specG posicion = do it "e1" $ posicion (0,1,0) `shouldBe` 2 it "e2" $ posicion (0,0,2) `shouldBe` 4 it "e3" $ posicion (0,1,1) `shouldBe` 5 spec :: Spec spec = do describe "def. 1" $ specG posicion1 describe "def. 2" $ specG posicion2 describe "def. 3" $ specG posicion3 describe "def. 4" $ specG posicion4 describe "def. 5" $ specG posicion5 -- La verificación es -- λ> verifica -- 15 examples, 0 failures -- 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) -- Propiedades -- =========== -- La 1ª propiedad es prop_posicion1 :: NonNegative Int -> Bool prop_posicion1 (NonNegative x) = posicion5 (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) = posicion5 (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) = posicion5 (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) = posicion5 (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. |
2. Soluciones en Python
|
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 |
from itertools import count, islice, takewhile from timeit import Timer, default_timer from typing import Iterator from hypothesis import given from hypothesis import strategies as st # 1ª solución # =========== # ternas es la lista ordenada de las ternas de números naturales. Por ejemplo, # >>> list(islice(ternas(), 9)) # [(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)] def ternas() -> Iterator[tuple[int, int, int]]: return ((x, y, n-x-y) for n in count() for x in range(n+1) for y in range(n-x+1)) def posicion1(t: tuple[int,int,int]) -> int: r = 0 for t1 in ternas(): if t == t1: return r r = r + 1 return -1 # 2ª solución # =========== def posicion2(t: tuple[int,int,int]) -> int: for (n,t1) in enumerate(ternas()): if t1 == t: return n return -1 # 3ª solución # =========== def posicion3(t: tuple[int,int,int]) -> int: return len(list(takewhile(lambda t1 : t1 != t, ternas()))) # Verificación # ============ def test_posicion() -> None: assert list(islice(ternas(), 9)) == \ [(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)] for posicion in [posicion1, posicion2, posicion3]: assert posicion((0,1,0)) == 2 assert posicion((0,0,2)) == 4 assert posicion((0,1,1)) == 5 print("Verificado") # La verificación es # >>> test_posicion() # Verificado # Equivalencia # ============ @given(st.integers(min_value=1, max_value=10), st.integers(min_value=1, max_value=10), st.integers(min_value=1, max_value=10)) def test_posicion_equiv(x: int, y: int, z: int) -> None: r = posicion1((x, y, z)) assert posicion2((x, y, z)) == r assert posicion3((x, y, z)) == r # La comprobación es # >>> test_posicion_equiv() # >>> # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('posicion1((147,46,116))') # 0.72 segundos # >>> tiempo('posicion2((147,46,116))') # 0.68 segundos # >>> tiempo('posicion3((147,46,116))') # 0.93 segundos # Propiedades # =========== # La 1ª propiedad es @given(st.integers(min_value=1, max_value=100)) def prop_posicion1(x: int) -> None: assert posicion1((x,0,0)) == x * (x**2 + 6*x + 11) // 6 # Su comprobación es # >>> prop_posicion1() # >>> # La 2ª propiedad es @given(st.integers(min_value=1, max_value=100)) def prop_posicion2(y: int) -> None: assert posicion1((0,y,0)) == y * (y**2 + 3*y + 8) // 6 # Su comprobación es # >>> prop_posicion2() # >>> # La 3ª propiedad es @given(st.integers(min_value=1, max_value=100)) def prop_posicion3(z: int) -> None: assert posicion1((0,0,z)) == z * (z**2 + 3*z + 2) // 6 # Su comprobación es # >>> prop_posicion3() # >>> # La 4ª propiedad es @given(st.integers(min_value=1, max_value=10)) def prop_posicion4(x: int) -> None: assert posicion1((x,x,x)) == x * (9 * x**2 + 14 * x + 7) // 2 # Su comprobación es # >>> prop_posicion4() # >>> |