{"id":6766,"date":"2022-03-17T06:00:43","date_gmt":"2022-03-17T04:00:43","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6766"},"modified":"2022-04-15T12:02:35","modified_gmt":"2022-04-15T10:02:35","slug":"numeracion-de-las-ternas-de-numeros-naturales","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeracion-de-las-ternas-de-numeros-naturales\/","title":{"rendered":"Numeraci\u00f3n de las ternas de n\u00fameros naturales"},"content":{"rendered":"

Las ternas de n\u00fameros naturales se pueden ordenar como sigue<\/p>\n

\n   (0,0,0),\n   (0,0,1),(0,1,0),(1,0,0),\n   (0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0),\n   (0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),...\n   ...\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   posicion :: (Int,Int,Int) -> Int\n<\/pre>\n
tal que (posicion (x,y,z))<\/code> es la posici\u00f3n de la terna de n\u00fameros naturales (x,y,z)<\/code> en la ordenaci\u00f3n anterior. Por ejemplo,<\/p>\n
\n   posicion (0,1,0)  ==  2\n   posicion (0,0,2)  ==  4\n   posicion (0,1,1)  ==  5\n<\/pre>\n
Comprobar con QuickCheck que<\/p>\n
    \n
  • la posici\u00f3n de (x,0,0) es x(x\u00b2+6x+11)\/6<\/li>\n
  • la posici\u00f3n de (0,y,0) es y(y\u00b2+3y+ 8)\/6<\/li>\n
  • la posici\u00f3n de (0,0,z) es z(z\u00b2+3z+ 2)\/6<\/li>\n
  • la posici\u00f3n de (x,x,x) es x(9x\u00b2+14x+7)\/2<\/li>\n<\/ul>\n
    Soluciones<\/h4>\n
    \nimport Data.List (elemIndex)\nimport Data.Maybe (fromJust)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nposicion1 :: (Int,Int,Int) -> Int\nposicion1 t = aux 0 ternas\n  where aux n (t':ts) | t' == t   = n\n                      | otherwise = aux (n+1) ts\n\n-- ternas es la lista ordenada de las ternas de n\u00fameros naturales. Por ejemplo,\n--    \u03bb> take 9 ternas\n--    [(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)]\nternas :: [(Int,Int,Int)]\nternas = [(x,y,n-x-y) | n <- [0..], x <- [0..n], y <- [0..n-x]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nposicion2 :: (Int,Int,Int) -> Int\nposicion2 t =\n  head [n | (n,t') <- zip [0..] ternas, t' == t]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nposicion3 :: (Int,Int,Int) -> Int\nposicion3 t = indice t ternas\n\n-- (indice x ys) es el \u00edndice de x en ys. Por ejemplo,\n--    indice 5 [0..]  ==  5\nindice :: Eq a => a -> [a] -> Int\nindice x ys = length (takeWhile (\/= x) ys)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nposicion4 :: (Int,Int,Int) -> Int\nposicion4 t = fromJust (elemIndex t ternas)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nposicion5 :: (Int,Int,Int) -> Int\nposicion5 = fromJust . (`elemIndex` ternas)\n\n-- Equivalencia\n-- ============\n\n-- La propiedad es\nprop_posicion_equiv :: NonNegative Int\n                    -> NonNegative Int\n                    -> NonNegative Int\n                    -> Bool\nprop_posicion_equiv (NonNegative x) (NonNegative y) (NonNegative z) =\n  all (== posicion1 (x,y,z))\n      [f (x,y,z) | f <- [ posicion2\n                        , posicion3\n                        , posicion4\n                        , posicion5 ]]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_posicion_equiv\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> posicion1 (147,46,116)\n--    5000000\n--    (5.84 secs, 2,621,428,184 bytes)\n--    \u03bb> posicion2 (147,46,116)\n--    5000000\n--    (3.63 secs, 2,173,230,200 bytes)\n--    \u03bb> posicion3 (147,46,116)\n--    5000000\n--    (2.48 secs, 1,453,229,880 bytes)\n--    \u03bb> posicion4 (147,46,116)\n--    5000000\n--    (1.91 secs, 1,173,229,840 bytes)\n--    \u03bb> posicion5 (147,46,116)\n--    5000000\n--    (1.94 secs, 1,173,229,960 bytes)\n\n-- En lo que sigue, usaremos la 5\u00aa definici\u00f3n\nposicion :: (Int,Int,Int) -> Int\nposicion = posicion5\n\n-- Propiedades\n-- ===========\n\n-- La 1\u00aa propiedad es\nprop_posicion1 :: NonNegative Int -> Bool\nprop_posicion1 (NonNegative x) =\n  posicion (x,0,0) == x * (x^2 + 6*x + 11) `div` 6\n\n-- Su comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_posicion1\n--    +++ OK, passed 100 tests.\n\n-- La 2\u00aa propiedad es\nprop_posicion2 :: NonNegative Int -> Bool\nprop_posicion2 (NonNegative y) =\n  posicion (0,y,0) == y * (y^2 + 3*y + 8) `div` 6\n\n-- Su comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_posicion2\n--    +++ OK, passed 100 tests.\n\n-- La 3\u00aa propiedad es\nprop_posicion3 :: NonNegative Int -> Bool\nprop_posicion3 (NonNegative z) =\n  posicion (0,0,z) == z * (z^2 + 3*z + 2) `div` 6\n\n-- Su comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_posicion3\n--    +++ OK, passed 100 tests.\n\n-- La 4\u00aa propiedad es\nprop_posicion4 :: NonNegative Int -> Bool\nprop_posicion4 (NonNegative x) =\n  posicion (x,x,x) == x * (9 * x^2 + 14 * x + 7) `div` 2\n\n-- Su comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_posicion4\n--    +++ OK, passed 100 tests.\n<\/pre>\n
    El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
    La elaboraci\u00f3n de las soluciones se muestra en el siguiente v\u00eddeo:<\/p>\n