{"id":6566,"date":"2022-01-28T05:00:33","date_gmt":"2022-01-28T03:00:33","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6566"},"modified":"2022-04-15T12:08:38","modified_gmt":"2022-04-15T10:08:38","slug":"sistema-factoradico-de-numeracion","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/sistema-factoradico-de-numeracion\/","title":{"rendered":"Sistema factor\u00e1dico de numeraci\u00f3n"},"content":{"rendered":"<p>El <a href=\"https:\/\/bit.ly\/3KQZRue\">sistema factor\u00e1dico<\/a> es un sistema num\u00e9rico basado en factoriales en el que el n-\u00e9simo d\u00edgito, empezando desde la derecha, debe ser multiplicado por n! Por ejemplo, el n\u00famero \u00ab341010\u00bb en el sistema factor\u00e1dico es 463 en el sistema decimal ya que<\/p>\n<pre lang=\"text\">\n   3\u00d75! + 4\u00d74! + 1\u00d73! + 0\u00d72! + 1\u00d71! + 0\u00d70! = 463\n<\/pre>\n<p>En este sistema num\u00e9rico, el d\u00edgito de m\u00e1s a la derecha es siempre 0, el segundo 0 o 1, el tercero 0,1 o 2 y as\u00ed sucesivamente.<\/p>\n<p>Con los d\u00edgitos del 0 al 9 el mayor n\u00famero que podemos codificar es el 10!-1 = 3628799. En cambio, si lo ampliamos con las letras A a Z podemos codificar hasta 36!-1 = 37199332678990121746799944815083519999999910.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   factoradicoAdecimal :: String -> Integer\n   decimalAfactoradico :: Integer -> String\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(factoradicoAdecimal cs) es el n\u00famero decimal correspondiente al n\u00famero factor\u00e1dico cs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> decimalAfactoradico 463\n     \"341010\"\n     \u03bb> decimalAfactoradico 2022\n     \"2441000\"\n     \u03bb> decimalAfactoradico 36288000\n     \"A0000000000\"\n     \u03bb> map decimalAfactoradico [1..10]\n     [\"10\",\"100\",\"110\",\"200\",\"210\",\"1000\",\"1010\",\"1100\",\"1110\",\"1200\"]\n     \u03bb> decimalAfactoradico 37199332678990121746799944815083519999999\n     \"3KXWVUTSRQPONMLKJIHGFEDCBA9876543210\"\n<\/pre>\n<ul>\n<li>(decimalAfactoradico n) es el n\u00famero factor\u00e1dico correpondiente al n\u00famero decimal n. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> factoradicoAdecimal \"341010\"\n     463\n     \u03bb> factoradicoAdecimal \"2441000\"\n     2022\n     \u03bb> factoradicoAdecimal \"A0000000000\"\n     36288000\n     \u03bb> map factoradicoAdecimal [\"10\",\"100\",\"110\",\"200\",\"210\",\"1000\",\"1010\",\"1100\",\"1110\",\"1200\"]\n     [1,2,3,4,5,6,7,8,9,10]\n     \u03bb> factoradicoAdecimal \"3KXWVUTSRQPONMLKJIHGFEDCBA9876543210\"\n     37199332678990121746799944815083519999999\n<\/pre>\n<p>Comprobar con QuickCheck que, para cualquier entero positivo n,<\/p>\n<pre lang=\"text\">\n   factoradicoAdecimal (decimalAfactoradico n) == n\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n{-# LANGUAGE TupleSections #-}\n\nimport Data.List (genericIndex, genericLength)\nimport qualified Data.Map as M\nimport Test.QuickCheck\nimport Test.Hspec\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nfactoradicoAdecimal1 :: String -> Integer\nfactoradicoAdecimal1 cs = sum (zipWith (*) xs ys)\n  where xs = map caracterAentero cs\n        n  = length cs\n        ys = reverse (take n facts)\n\n-- (caracterAentero c) es la posici\u00f3n del car\u00e1cter c en la lista de\n-- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,\n--    caracterAentero '0'  ==  0\n--    caracterAentero '1'  ==  1\n--    caracterAentero '9'  ==  9\n--    caracterAentero 'A'  ==  10\n--    caracterAentero 'B'  ==  11\n--    caracterAentero 'Z'  ==  35\ncaracterAentero :: Char -> Integer\ncaracterAentero c =\n  head [n | (n,x) <- zip [0..] caracteres, x == c]\n\n-- caracteres es la lista de caracteres\n-- ['0', '1',..., '9', 'A', 'B',..., 'Z']\ncaracteres :: String\ncaracteres = ['0'..'9'] ++ ['A'..'Z']\n\n-- facts es la lista de los factoriales. Por ejemplo,\n--    \u03bb> take 12 facts\n--    [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800]\nfacts :: [Integer]\nfacts = scanl (*) 1 [1..]\n\ndecimalAfactoradico1 :: Integer -> String\ndecimalAfactoradico1 n = aux n (reverse (takeWhile (<=n) facts))\n  where aux 0 xs     = ['0' | _ <- xs]\n        aux m (x:xs) = enteroAcaracter (m `div` x) : aux (m `mod` x) xs\n\n-- (enteroAcaracter k) es el k-\u00e9simo elemento de la lista\n-- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,\n--    enteroAcaracter 0   ==  '0'\n--    enteroAcaracter 1   ==  '1'\n--    enteroAcaracter 9   ==  '9'\n--    enteroAcaracter 10  ==  'A'\n--    enteroAcaracter 11  ==  'B'\n--    enteroAcaracter 35  ==  'Z'\nenteroAcaracter :: Integer -> Char\nenteroAcaracter k = caracteres `genericIndex` k\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nfactoradicoAdecimal2 :: String -> Integer\nfactoradicoAdecimal2 cs = sum (zipWith (*) xs ys)\n    where xs = map caracterAentero2 cs\n          n  = length cs\n          ys = reverse (take n facts)\n\n-- (caracterAentero2 c) es la posici\u00f3n del car\u00e1cter c en la lista de\n-- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,\n--    caracterAentero2 '0'  ==  0\n--    caracterAentero2 '1'  ==  1\n--    caracterAentero2 '9'  ==  9\n--    caracterAentero2 'A'  ==  10\n--    caracterAentero2 'B'  ==  11\n--    caracterAentero2 'Z'  ==  35\ncaracterAentero2 :: Char -> Integer\ncaracterAentero2 c = caracteresEnteros M.! c\n\n-- caracteresEnteros es el diccionario cuyas claves son los caracteres y\n-- las claves son los n\u00fameros de 0 a 35.\ncaracteresEnteros :: M.Map Char Integer\ncaracteresEnteros = M.fromList (zip (['0'..'9'] ++ ['A'..'Z']) [0..])\n\ndecimalAfactoradico2 :: Integer -> String\ndecimalAfactoradico2 n = aux n (reverse (takeWhile (<=n) facts))\n    where aux 0 xs     = ['0' | _ <- xs]\n          aux m (x:xs) = enteroAcaracter2 (m `div` x) : aux (m `mod` x) xs\n\n-- (enteroAcaracter2 k) es el k-\u00e9simo elemento de la lista\n-- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,\n--    enteroAcaracter2 0   ==  '0'\n--    enteroAcaracter2 1   ==  '1'\n--    enteroAcaracter2 9   ==  '9'\n--    enteroAcaracter2 10  ==  'A'\n--    enteroAcaracter2 11  ==  'B'\n--    enteroAcaracter2 35  ==  'Z'\nenteroAcaracter2 :: Integer -> Char\nenteroAcaracter2 k = enterosCaracteres M.! k\n\n-- enterosCaracteres es el diccionario cuyas claves son los n\u00famero de 0\n-- a 35 y las claves son los caracteres.\nenterosCaracteres :: M.Map Integer Char\nenterosCaracteres = M.fromList (zip [0..] caracteres)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nfactoradicoAdecimal3 :: String -> Integer\nfactoradicoAdecimal3 cs =\n  sum (zipWith (*) facts (reverse (map caracterAentero3 cs)))\n\n-- (caracterAentero3 c) es la posici\u00f3n del car\u00e1cter c en la lista de\n-- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,\n--    caracterAentero3 '0'  ==  0\n--    caracterAentero3 '1'  ==  1\n--    caracterAentero3 '9'  ==  9\n--    caracterAentero3 'A'  ==  10\n--    caracterAentero3 'B'  ==  11\n--    caracterAentero3 'Z'  ==  35\ncaracterAentero3 :: Char -> Integer\ncaracterAentero3 c =\n  genericLength (takeWhile (\/= c) caracteres)\n\ndecimalAfactoradico3 :: Integer -> String\ndecimalAfactoradico3 n = aux \"\" 2 (n, 0)\n  where aux s _ (0, 0) = s\n        aux s n (d, r) = aux (enteroAcaracter3 r: s) (n + 1) (d `divMod` n)\n\n-- (enteroAcaracter3 k) es el k-\u00e9simo elemento de la lista\n-- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,\n--    enteroAcaracter3 0   ==  '0'\n--    enteroAcaracter3 1   ==  '1'\n--    enteroAcaracter3 9   ==  '9'\n--    enteroAcaracter3 10  ==  'A'\n--    enteroAcaracter3 11  ==  'B'\n--    enteroAcaracter3 35  ==  'Z'\nenteroAcaracter3 :: Integer -> Char\nenteroAcaracter3 n =\n  caracteres !! (fromInteger n)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nfactoradicoAdecimal4 :: String -> Integer\nfactoradicoAdecimal4 =\n  sum . zipWith (*) facts . reverse . map caracterAentero4\n\n-- (caracterAentero4 c) es la posici\u00f3n del car\u00e1cter c en la lista de\n-- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,\n--    caracterAentero4 '0'  ==  0\n--    caracterAentero4 '1'  ==  1\n--    caracterAentero4 '9'  ==  9\n--    caracterAentero4 'A'  ==  10\n--    caracterAentero4 'B'  ==  11\n--    caracterAentero4 'Z'  ==  35\ncaracterAentero4 :: Char -> Integer\ncaracterAentero4 =\n  genericLength . flip takeWhile caracteres . (\/=)\n\ndecimalAfactoradico4 :: Integer -> String\ndecimalAfactoradico4 = f \"\" 2 . (, 0)\n  where f s _ (0, 0) = s\n        f s n (d, r) = f (enteroAcaracter4 r: s) (n + 1) (d `divMod` n)\n\n-- (enteroAcaracter4 k) es el k-\u00e9simo elemento de la lista\n-- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,\n--    enteroAcaracter4 0   ==  '0'\n--    enteroAcaracter4 1   ==  '1'\n--    enteroAcaracter4 9   ==  '9'\n--    enteroAcaracter4 10  ==  'A'\n--    enteroAcaracter4 11  ==  'B'\n--    enteroAcaracter4 35  ==  'Z'\nenteroAcaracter4 :: Integer -> Char\nenteroAcaracter4 = (caracteres `genericIndex`)\n\n-- Propiedad de inverso\n-- ====================\n\nprop_factoradico :: Integer -> Property\nprop_factoradico n =\n  n >= 0 ==>\n  factoradicoAdecimal1 (decimalAfactoradico1 n) == n &&\n  factoradicoAdecimal2 (decimalAfactoradico2 n) == n &&\n  factoradicoAdecimal3 (decimalAfactoradico3 n) == n &&\n  factoradicoAdecimal4 (decimalAfactoradico4 n) == n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_factoradico\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (decimalAfactoradico1 (10^300000))\n--    68191\n--    (2.46 secs, 9,088,634,744 bytes)\n--    \u03bb> length (decimalAfactoradico2 (10^300000))\n--    68191\n--    (2.36 secs, 9,088,634,800 bytes)\n--    \u03bb> length (decimalAfactoradico3 (10^300000))\n--    68191\n--    (2.18 secs, 4,490,856,416 bytes)\n--    \u03bb> length (decimalAfactoradico4 (10^300000))\n--    68191\n--    (1.98 secs, 4,490,311,536 bytes)\n--\n--    \u03bb> length (show (factoradicoAdecimal1 (show (10^50000))))\n--    213237\n--    (0.93 secs, 2,654,156,680 bytes)\n--    \u03bb> length (show (factoradicoAdecimal2 (show (10^50000))))\n--    213237\n--    (0.51 secs, 2,633,367,168 bytes)\n--    \u03bb> length (show (factoradicoAdecimal3 (show (10^50000))))\n--    213237\n--    (0.93 secs, 2,635,792,192 bytes)\n--    \u03bb> length (show (factoradicoAdecimal4 (show (10^50000))))\n--    213237\n--    (0.43 secs, 2,636,996,848 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Sistema_factoradico_de_numeracion.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>El sistema factor\u00e1dico es un sistema num\u00e9rico basado en factoriales en el que el n-\u00e9simo d\u00edgito, empezando desde la derecha, debe ser multiplicado por n! Por ejemplo, el n\u00famero \u00ab341010\u00bb en el sistema factor\u00e1dico es 463 en el sistema decimal ya que 3\u00d75! + 4\u00d74! + 1\u00d73! + 0\u00d72! + 1\u00d71! + 0\u00d70! = 463&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[2],"tags":[8,498,396,415,11,6,521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6566"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=6566"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6566\/revisions"}],"predecessor-version":[{"id":6680,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6566\/revisions\/6680"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6566"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6566"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6566"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}