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 |
λ> 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 |
- (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 |
λ> 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" |
Comprobar con QuickCheck que, para cualquier entero positivo n,
1 |
factoradicoAdecimal (decimalAfactoradico n) == n |
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 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 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 |
module Sistema_factoradico_de_numeracion where import Data.List (genericIndex, genericLength) import qualified Data.Map as M ((!), Map, fromList) import Test.Hspec (Spec, describe, hspec, it, shouldBe) import Test.QuickCheck -- 1ª definición de factoradicoAdecimal -- ==================================== 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..] -- 2ª definición de factoradicoAdecimal -- ==================================== 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..]) -- 3ª definición de factoradicoAdecimal -- ==================================== 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) -- 4ª definición de factoradicoAdecimal -- ==================================== 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 . (/=) -- 1ª definición de decimalAfactoradico -- ==================================== 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ª definición de decimalAfactoradico -- ==================================== 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ª definición de decimalAfactoradico -- ==================================== decimalAfactoradico3 :: Integer -> String decimalAfactoradico3 n = aux "" 2 (n, 0) where aux s _ (0, 0) = s aux s m (d, r) = aux (enteroAcaracter3 r: s) (m + 1) (d `divMod` m) -- (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ª definición de decimalAfactoradico -- ==================================== 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`) -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG1 :: (String -> Integer) -> Spec specG1 factoradicoAdecimal = do it "e1" $ factoradicoAdecimal "341010" `shouldBe` 463 it "e2" $ factoradicoAdecimal "2441000" `shouldBe` 2022 it "e3" $ factoradicoAdecimal "A0000000000" `shouldBe` 36288000 specG2 :: (Integer -> String) -> Spec specG2 decimalAfactoradico = do it "e1" $ decimalAfactoradico 463 `shouldBe` "341010" it "e2" $ decimalAfactoradico 2022 `shouldBe` "2441000" it "e3" $ decimalAfactoradico 36288000 `shouldBe` "A0000000000" spec :: Spec spec = do describe "def. 1" $ specG1 factoradicoAdecimal1 describe "def. 2" $ specG1 factoradicoAdecimal2 describe "def. 3" $ specG1 factoradicoAdecimal3 describe "def. 4" $ specG1 factoradicoAdecimal4 describe "def. 1" $ specG2 decimalAfactoradico1 describe "def. 2" $ specG2 decimalAfactoradico2 describe "def. 3" $ specG2 decimalAfactoradico3 describe "def. 4" $ specG2 decimalAfactoradico4 -- La verificación es -- λ> verifica -- -- 24 examples, 0 failures -- 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; 101 discarded. -- 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) |
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 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 |
from itertools import count, takewhile from math import factorial from typing import Iterator from hypothesis import given from hypothesis import strategies as st # 1ª definición de factoradicoAdecimal # ==================================== # 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 def caracterAentero(c: str) -> int: if c.isdigit(): return int(c) return ord(c) - ord('A') + 10 def factoradicoAdecimal1(cs: str) -> int: xs = map(caracterAentero, cs) n = len(cs) ys = reversed([factorial(k) for k in range(n)]) return sum((x * y for (x, y) in zip(xs, ys))) # 2ª definición de factoradicoAdecimal # ==================================== # caracteres es la cadena de los caracteres. caracteres: str = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' # caracteresEnteros es el diccionario cuyas claves son los caracteres y # los valores son los números de 0 a 35. caracteresEnteros: dict[str, int] = {c: i for i, c in enumerate(caracteres)} # 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 def caracterAentero2(c: str) -> int: return caracteresEnteros[c] def factoradicoAdecimal2(cs: str) -> int: xs = map(caracterAentero2, cs) n = len(cs) ys = reversed([factorial(k) for k in range(n)]) return sum((x * y for (x, y) in zip(xs, ys))) # 3ª definición de factoradicoAdecimal # ==================================== # 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 def caracterAentero3(c: str) -> int: return len(list(takewhile(lambda x: x != c, caracteres))) def factoradicoAdecimal3(cs: str) -> int: return sum(x * y for x, y in zip([factorial(k) for k in range(len(cs))], reversed(list(map(caracterAentero3, cs))))) # 1ª definición de decimalAfactoradico # ==================================== # 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' def enteroAcaracter(k: int) -> str: return caracteres[k] # facts() es la lista de los factoriales. Por ejemplo, # >>> list(takewhile(lambda x : x < 900, facts())) # [1, 1, 2, 6, 24, 120, 720] def facts() -> Iterator[int]: return (factorial(n) for n in count()) def decimalAfactoradico1(n: int) -> str: def aux(m: int, xs: list[int]) -> str: if m == 0: return "0" * len(xs) y, *ys = xs print(m, y, m // y) return enteroAcaracter(m // y) + aux(m % y, ys) return aux(n, list(reversed(list(takewhile(lambda x : x <= n, facts()))))) # 2ª definición de decimalAfactoradico # ==================================== # enterosCaracteres es el diccionario cuyas claves son los número de 0 # a 35 y las claves son los caracteres. enterosCaracteres: dict[int, str] = dict(enumerate(caracteres)) # 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' def enteroAcaracter2(k: int) -> str: return enterosCaracteres[k] def decimalAfactoradico2(n: int) -> str: def aux(m: int, xs: list[int]) -> str: if m == 0: return "0" * len(xs) y, *ys = xs return enteroAcaracter2(m // y) + aux(m % y, ys) return aux(n, list(reversed(list(takewhile(lambda x : x <= n, facts()))))) # 3ª definición de decimalAfactoradico # ==================================== # 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' def enteroAcaracter3(n: int) -> str: return caracteres[n] def decimalAfactoradico3(n: int) -> str: def aux(m: int, xs: list[int]) -> str: if m == 0: return "0" * len(xs) y, *ys = xs return enteroAcaracter3(m // y) + aux(m % y, ys) return aux(n, list(reversed(list(takewhile(lambda x : x <= n, facts()))))) # Verificación # ============ def test_factoradico() -> None: for factoradicoAdecimal in [factoradicoAdecimal1, factoradicoAdecimal2, factoradicoAdecimal3]: assert factoradicoAdecimal("341010") == 463 assert factoradicoAdecimal("2441000") == 2022 assert factoradicoAdecimal("A0000000000") == 36288000 for decimalAfactoradico in [decimalAfactoradico1, decimalAfactoradico2, decimalAfactoradico3]: assert decimalAfactoradico(463) == "341010" assert decimalAfactoradico(2022) == "2441000" assert decimalAfactoradico(36288000) == "A0000000000" print("Verificado") # La verificación es # >>> test_factoradico() # Verificado # Propiedad de inverso # ==================== @given(st.integers(min_value=0, max_value=1000)) def test_factoradico_equiv(n: int) -> None: assert factoradicoAdecimal1(decimalAfactoradico1(n)) == n assert factoradicoAdecimal2(decimalAfactoradico3(n)) == n assert factoradicoAdecimal3(decimalAfactoradico3(n)) == n # La comprobación es # >>> test_factoradico_equiv() # >>> |