Sistema factorádico de numeración
El sistema factorádico es un sistema numérico basado en factoriales en el que el n-ésimo dígito, empezando desde la derecha, debe ser multiplicado por n! Por ejemplo, el número «341010» en el sistema factorádico es 463 en el sistema decimal ya que
1 |
3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = 463 |
En este sistema numérico, el dígito de más a la derecha es siempre 0, el segundo 0 o 1, el tercero 0,1 o 2 y así sucesivamente.
Con los dígitos del 0 al 9 el mayor número 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.
Definir las funciones
1 2 |
factoradicoAdecimal :: String -> Integer decimalAfactoradico :: Integer -> String |
tales que
- (factoradicoAdecimal cs) es el número decimal correspondiente al número factorádico cs. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 |
λ> decimalAfactoradico 463 "341010" λ> decimalAfactoradico 2022 "2441000" λ> decimalAfactoradico 36288000 "A0000000000" λ> map decimalAfactoradico [1..10] ["10","100","110","200","210","1000","1010","1100","1110","1200"] λ> decimalAfactoradico 37199332678990121746799944815083519999999 "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210" |
- (decimalAfactoradico n) es el número factorádico correpondiente al número decimal n. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 |
λ> factoradicoAdecimal "341010" 463 λ> factoradicoAdecimal "2441000" 2022 λ> factoradicoAdecimal "A0000000000" 36288000 λ> map factoradicoAdecimal ["10","100","110","200","210","1000","1010","1100","1110","1200"] [1,2,3,4,5,6,7,8,9,10] λ> factoradicoAdecimal "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210" 37199332678990121746799944815083519999999 |
Comprobar con QuickCheck que, para cualquier entero positivo n,
1 |
factoradicoAdecimal (decimalAfactoradico n) == n |
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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 |
{-# LANGUAGE TupleSections #-} import Data.List (genericIndex, genericLength) import qualified Data.Map as M import Test.QuickCheck import Test.Hspec -- 1ª solución -- =========== factoradicoAdecimal1 :: String -> Integer factoradicoAdecimal1 cs = sum (zipWith (*) xs ys) where xs = map caracterAentero cs n = length cs ys = reverse (take n facts) -- (caracterAentero c) es la posición del carácter c en la lista de -- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo, -- caracterAentero '0' == 0 -- caracterAentero '1' == 1 -- caracterAentero '9' == 9 -- caracterAentero 'A' == 10 -- caracterAentero 'B' == 11 -- caracterAentero 'Z' == 35 caracterAentero :: Char -> Integer caracterAentero c = head [n | (n,x) <- zip [0..] caracteres, x == c] -- caracteres es la lista de caracteres -- ['0', '1',..., '9', 'A', 'B',..., 'Z'] caracteres :: String caracteres = ['0'..'9'] ++ ['A'..'Z'] -- facts es la lista de los factoriales. Por ejemplo, -- λ> take 12 facts -- [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800] facts :: [Integer] facts = scanl (*) 1 [1..] decimalAfactoradico1 :: Integer -> String decimalAfactoradico1 n = aux n (reverse (takeWhile (<=n) facts)) where aux 0 xs = ['0' | _ <- xs] aux m (x:xs) = enteroAcaracter (m `div` x) : aux (m `mod` x) xs -- (enteroAcaracter k) es el k-ésimo elemento de la lista -- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo, -- enteroAcaracter 0 == '0' -- enteroAcaracter 1 == '1' -- enteroAcaracter 9 == '9' -- enteroAcaracter 10 == 'A' -- enteroAcaracter 11 == 'B' -- enteroAcaracter 35 == 'Z' enteroAcaracter :: Integer -> Char enteroAcaracter k = caracteres `genericIndex` k -- 2ª solución -- =========== factoradicoAdecimal2 :: String -> Integer factoradicoAdecimal2 cs = sum (zipWith (*) xs ys) where xs = map caracterAentero2 cs n = length cs ys = reverse (take n facts) -- (caracterAentero2 c) es la posición del carácter c en la lista de -- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo, -- caracterAentero2 '0' == 0 -- caracterAentero2 '1' == 1 -- caracterAentero2 '9' == 9 -- caracterAentero2 'A' == 10 -- caracterAentero2 'B' == 11 -- caracterAentero2 'Z' == 35 caracterAentero2 :: Char -> Integer caracterAentero2 c = caracteresEnteros M.! c -- caracteresEnteros es el diccionario cuyas claves son los caracteres y -- las claves son los números de 0 a 35. caracteresEnteros :: M.Map Char Integer caracteresEnteros = M.fromList (zip (['0'..'9'] ++ ['A'..'Z']) [0..]) decimalAfactoradico2 :: Integer -> String decimalAfactoradico2 n = aux n (reverse (takeWhile (<=n) facts)) where aux 0 xs = ['0' | _ <- xs] aux m (x:xs) = enteroAcaracter2 (m `div` x) : aux (m `mod` x) xs -- (enteroAcaracter2 k) es el k-ésimo elemento de la lista -- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo, -- enteroAcaracter2 0 == '0' -- enteroAcaracter2 1 == '1' -- enteroAcaracter2 9 == '9' -- enteroAcaracter2 10 == 'A' -- enteroAcaracter2 11 == 'B' -- enteroAcaracter2 35 == 'Z' enteroAcaracter2 :: Integer -> Char enteroAcaracter2 k = enterosCaracteres M.! k -- enterosCaracteres es el diccionario cuyas claves son los número de 0 -- a 35 y las claves son los caracteres. enterosCaracteres :: M.Map Integer Char enterosCaracteres = M.fromList (zip [0..] caracteres) -- 3ª solución -- =========== factoradicoAdecimal3 :: String -> Integer factoradicoAdecimal3 cs = sum (zipWith (*) facts (reverse (map caracterAentero3 cs))) -- (caracterAentero3 c) es la posición del carácter c en la lista de -- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo, -- caracterAentero3 '0' == 0 -- caracterAentero3 '1' == 1 -- caracterAentero3 '9' == 9 -- caracterAentero3 'A' == 10 -- caracterAentero3 'B' == 11 -- caracterAentero3 'Z' == 35 caracterAentero3 :: Char -> Integer caracterAentero3 c = genericLength (takeWhile (/= c) caracteres) decimalAfactoradico3 :: Integer -> String decimalAfactoradico3 n = aux "" 2 (n, 0) where aux s _ (0, 0) = s aux s n (d, r) = aux (enteroAcaracter3 r: s) (n + 1) (d `divMod` n) -- (enteroAcaracter3 k) es el k-ésimo elemento de la lista -- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo, -- enteroAcaracter3 0 == '0' -- enteroAcaracter3 1 == '1' -- enteroAcaracter3 9 == '9' -- enteroAcaracter3 10 == 'A' -- enteroAcaracter3 11 == 'B' -- enteroAcaracter3 35 == 'Z' enteroAcaracter3 :: Integer -> Char enteroAcaracter3 n = caracteres !! (fromInteger n) -- 4ª solución -- =========== factoradicoAdecimal4 :: String -> Integer factoradicoAdecimal4 = sum . zipWith (*) facts . reverse . map caracterAentero4 -- (caracterAentero4 c) es la posición del carácter c en la lista de -- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo, -- caracterAentero4 '0' == 0 -- caracterAentero4 '1' == 1 -- caracterAentero4 '9' == 9 -- caracterAentero4 'A' == 10 -- caracterAentero4 'B' == 11 -- caracterAentero4 'Z' == 35 caracterAentero4 :: Char -> Integer caracterAentero4 = genericLength . flip takeWhile caracteres . (/=) decimalAfactoradico4 :: Integer -> String decimalAfactoradico4 = f "" 2 . (, 0) where f s _ (0, 0) = s f s n (d, r) = f (enteroAcaracter4 r: s) (n + 1) (d `divMod` n) -- (enteroAcaracter4 k) es el k-ésimo elemento de la lista -- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo, -- enteroAcaracter4 0 == '0' -- enteroAcaracter4 1 == '1' -- enteroAcaracter4 9 == '9' -- enteroAcaracter4 10 == 'A' -- enteroAcaracter4 11 == 'B' -- enteroAcaracter4 35 == 'Z' enteroAcaracter4 :: Integer -> Char enteroAcaracter4 = (caracteres `genericIndex`) -- Propiedad de inverso -- ==================== prop_factoradico :: Integer -> Property prop_factoradico n = n >= 0 ==> factoradicoAdecimal1 (decimalAfactoradico1 n) == n && factoradicoAdecimal2 (decimalAfactoradico2 n) == n && factoradicoAdecimal3 (decimalAfactoradico3 n) == n && factoradicoAdecimal4 (decimalAfactoradico4 n) == n -- La comprobación es -- λ> quickCheck prop_factoradico -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (decimalAfactoradico1 (10^300000)) -- 68191 -- (2.46 secs, 9,088,634,744 bytes) -- λ> length (decimalAfactoradico2 (10^300000)) -- 68191 -- (2.36 secs, 9,088,634,800 bytes) -- λ> length (decimalAfactoradico3 (10^300000)) -- 68191 -- (2.18 secs, 4,490,856,416 bytes) -- λ> length (decimalAfactoradico4 (10^300000)) -- 68191 -- (1.98 secs, 4,490,311,536 bytes) -- -- λ> length (show (factoradicoAdecimal1 (show (10^50000)))) -- 213237 -- (0.93 secs, 2,654,156,680 bytes) -- λ> length (show (factoradicoAdecimal2 (show (10^50000)))) -- 213237 -- (0.51 secs, 2,633,367,168 bytes) -- λ> length (show (factoradicoAdecimal3 (show (10^50000)))) -- 213237 -- (0.93 secs, 2,635,792,192 bytes) -- λ> length (show (factoradicoAdecimal4 (show (10^50000)))) -- 213237 -- (0.43 secs, 2,636,996,848 bytes) |
El código se encuentra en GitHub.
4 Comentarios