TAD de los polinomios: Transformaciones entre las representaciones dispersa y densa
Definir las funciones
|
1 2 |
densaAdispersa :: (Num a, Eq a) => [a] -> [(Int,a)] dispersaAdensa :: (Num a, Eq a) => [(Int,a)] -> [a] |
tales que
densaAdispersa xses la representación dispersa del polinomio cuya representación densa esxs. Por ejemplo,
|
1 2 |
λ> densaAdispersa [9,0,0,5,0,4,7] [(6,9),(3,5),(1,4),(0,7)] |
dispersaAdensa pses la representación densa del polinomio cuya representación dispersa esps. Por ejemplo,
|
1 2 |
λ> dispersaAdensa [(6,9),(3,5),(1,4),(0,7)] [9,0,0,5,0,4,7] |
Comprobar con QuickCheck que las funciones densaAdispersa y dispersaAdensa son inversas.
Soluciones
A continuación se muestran las soluciones en Haskell y las 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 |
import Data.List (nub, sort) import Test.QuickCheck -- 1ª definición de densaAdispersa -- =============================== densaAdispersa :: (Num a, Eq a) => [a] -> [(Int,a)] densaAdispersa xs = [(m,a) | (m,a) <- zip [n-1,n-2..] xs, a /= 0] where n = length xs -- 2ª definición de densaAdispersa -- =============================== densaAdispersa2 :: (Num a, Eq a) => [a] -> [(Int,a)] densaAdispersa2 xs = reverse (aux (reverse xs) 0) where aux [] _ = [] aux (0:ys) n = aux ys (n+1) aux (y:ys) n = (n,y) : aux ys (n+1) -- Comprobación de equivalencia de densaAdispersa -- ============================================== -- La propiedad es prop_densaAdispersa :: [Int] -> Bool prop_densaAdispersa xs = densaAdispersa xs == densaAdispersa2 xs -- La comprobación es -- λ> quickCheck prop_densaAdispersa -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> densaAdispersa (5 : replicate (10^7) 0) -- [(10000000,5)] -- (4.54 secs, 3,280,572,504 bytes) -- λ> densaAdispersa2 (5 : replicate (10^7) 0) -- [(10000000,5)] -- (7.35 secs, 3,696,968,576 bytes) -- 1ª definición de dispersaAdensa -- =============================== dispersaAdensa :: (Num a, Eq a) => [(Int,a)] -> [a] dispersaAdensa [] = [] dispersaAdensa [(n,a)] = a : replicate n 0 dispersaAdensa ((n,a):(m,b):ps) = a : replicate (n-m-1) 0 ++ dispersaAdensa ((m,b):ps) -- 2ª definición de dispersaAdensa -- =============================== dispersaAdensa2 :: (Num a, Eq a) => [(Int,a)] -> [a] dispersaAdensa2 [] = [] dispersaAdensa2 ps@((n,_):_) = [coeficiente ps m | m <- [n,n-1..0]] -- (coeficiente ps n) es el coeficiente del término de grado n en el -- polinomio cuya representación densa es ps. Por ejemplo, -- coeficiente [(6,9),(3,5),(1,4),(0,7)] 3 == 5 -- coeficiente [(6,9),(3,5),(1,4),(0,7)] 4 == 0 coeficiente :: (Num a, Eq a) => [(Int,a)] -> Int -> a coeficiente [] _ = 0 coeficiente ((m,a):ps) n | n > m = 0 | n == m = a | otherwise = coeficiente ps n -- Comprobación de equivalencia de dispersaAdensa -- ============================================== -- Tipo de las representaciones dispersas de polinomios. newtype Dispersa = Dis [(Int,Int)] deriving Show -- dispersaArbitraria es un generador de representaciones dispersas de -- polinomios. Por ejemplo, -- λ> sample dispersaArbitraria -- Dis [] -- Dis [] -- Dis [(3,-2),(2,0),(0,3)] -- Dis [(6,1),(4,-2),(3,4),(2,-4)] -- Dis [] -- Dis [(5,-7)] -- Dis [(12,5),(11,-8),(10,3),(8,-10),(7,-5),(4,12),(3,6),(2,-8),(1,11)] -- Dis [(7,-2),(2,-8)] -- Dis [(14,-15)] -- Dis [(17,5),(16,1),(15,-1),(14,10),(13,5),(12,-15),(9,12),(6,14)] -- Dis [(19,17),(12,7),(8,-3),(7,13),(5,-2),(4,7)] dispersaArbitraria :: Gen Dispersa dispersaArbitraria = do (xs, ys) <- arbitrary let xs' = nub (reverse (sort (map abs xs))) ys' = filter (/= 0) ys return (Dis (zip xs' ys')) -- Dispersa está contenida en Arbitrary instance Arbitrary Dispersa where arbitrary = dispersaArbitraria -- La propiedad es prop_dispersaAdensa :: Dispersa -> Bool prop_dispersaAdensa (Dis xs) = dispersaAdensa xs == dispersaAdensa2 xs -- La comprobación es -- λ> quickCheck prop_dispersaAdensa -- +++ OK, passed 100 tests. -- Comparación de eficiencia de dispersaAdensa -- =========================================== -- La comparación es -- λ> length (dispersaAdensa [(10^7,5)]) -- 10000001 -- (0.11 secs, 560,566,848 bytes) -- λ> length (dispersaAdensa2 [(10^7,5)]) -- 10000001 -- (2.51 secs, 2,160,567,112 bytes) -- Propiedad -- ========= -- Tipo de las representaciones densas de polinomios. newtype Densa = Den [Int] deriving Show -- densaArbitraria es un generador de representaciones dispersas de -- polinomios. Por ejemplo, -- λ> sample densaArbitraria -- Den [] -- Den [] -- Den [] -- Den [-6,6,5,-3] -- Den [] -- Den [8,-7,-10,8,-10,-4,10,6,10] -- Den [-6,2,11,-4,-9,-5,9,2,2,9] -- Den [-6,9,-2] -- Den [-1,-7,15,1,5,-2,13,16,8,7,2,16,-2,16,-7,4] -- Den [8,13,-4,-2,-10,3,5,-4,-6,13,-9,-12,8,11,9,-18,12,10] -- Den [-1,-2,11,17,-7,13,-12,-19,16,-10,-18,-19,1,-4,-17,10,1,10] densaArbitraria :: Gen Densa densaArbitraria = do ys <- arbitrary let ys' = dropWhile (== 0) ys return (Den ys') -- Dispersa está contenida en Arbitrary instance Arbitrary Densa where arbitrary = densaArbitraria -- La primera propiedad es prop_dispersaAdensa_densaAdispersa :: Densa -> Bool prop_dispersaAdensa_densaAdispersa (Den xs) = dispersaAdensa (densaAdispersa xs) == xs -- La comprobación es -- λ> quickCheck prop_dispersaAdensa_densaAdispersa -- +++ OK, passed 100 tests. -- La segunda propiedad es prop_densaAdispersa_dispersaAdensa :: Dispersa -> Bool prop_densaAdispersa_dispersaAdensa (Dis ps) = densaAdispersa (dispersaAdensa ps) == ps -- La comprobación es -- λ> quickCheck prop_densaAdispersa_dispersaAdensa -- +++ OK, passed 100 tests. |
|
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 |
from itertools import dropwhile from typing import TypeVar from hypothesis import given from hypothesis import strategies as st A = TypeVar('A', int, float, complex) # 1ª definición de densaAdispersa # =============================== def densaAdispersa(xs: list[A]) -> list[tuple[int, A]]: n = len(xs) return [(m, a) for (m, a) in zip(range(n-1, -1, -1), xs) if a != 0] # 2ª definición de densaAdispersa # =============================== def densaAdispersa2(xs: list[A]) -> list[tuple[int, A]]: def aux(xs: list[A], n: int) -> list[tuple[int, A]]: if not xs: return [] if xs[0] == 0: return aux(xs[1:], n + 1) return [(n, xs[0])] + aux(xs[1:], n + 1) return list(reversed(aux(list(reversed(xs)), 0))) # 3ª definición de densaAdispersa # =============================== def densaAdispersa3(xs: list[A]) -> list[tuple[int, A]]: r = [] n = len(xs) - 1 for x in xs: if x != 0: r.append((n, x)) n -= 1 return r # Comprobación de equivalencia de densaAdispersa # ============================================== # normalDensa(ps) es la representación dispersa de un polinomio. def normalDensa(xs: list[A]) -> list[A]: return list(dropwhile(lambda x: x == 0, xs)) # densaAleatoria() genera representaciones densas de polinomios # aleatorios. Por ejemplo, # >>> densaAleatoria().example() # [-5, 9, -6, -5, 7, -5, -1, 9] # >>> densaAleatoria().example() # [-4, 9, -3, -3, -5, 0, 6, -8, 8, 6, 0, -9] # >>> densaAleatoria().example() # [-3, -1, 2, 0, -9] def densaAleatoria() -> st.SearchStrategy[list[int]]: return st.lists(st.integers(min_value=-9, max_value=9))\ .map(normalDensa) # La propiedad es @given(xs=densaAleatoria()) def test_densaADispersa(xs: list[int]) -> None: r = densaAdispersa(xs) assert densaAdispersa2(xs) == r assert densaAdispersa3(xs) == r # 1ª definición de dispersaAdensa # =============================== def dispersaAdensa(ps: list[tuple[int, A]]) -> list[A]: if not ps: return [] if len(ps) == 1: return [ps[0][1]] + [0] * ps[0][0] (n, a) = ps[0] (m, _) = ps[1] return [a] + [0] * (n-m-1) + dispersaAdensa(ps[1:]) # 2ª definición de dispersaAdensa # =============================== # coeficiente(ps, n) es el coeficiente del término de grado n en el # polinomio cuya representación densa es ps. Por ejemplo, # coeficiente([(6, 9), (3, 5), (1, 4), (0, 7)], 3) == 5 # coeficiente([(6, 9), (3, 5), (1, 4), (0, 7)], 4) == 0 def coeficiente(ps: list[tuple[int, A]], n: int) -> A: if not ps: return 0 (m, a) = ps[0] if n > m: return 0 if n == m: return a return coeficiente(ps[1:], n) def dispersaAdensa2(ps: list[tuple[int, A]]) -> list[A]: if not ps: return [] n = ps[0][0] return [coeficiente(ps, m) for m in range(n, -1, -1)] # 3ª definición de dispersaAdensa # =============================== def dispersaAdensa3(ps: list[tuple[int, A]]) -> list[A]: if not ps: return [] n = ps[0][0] r: list[A] = [0] * (n + 1) for (m, a) in ps: r[n-m] = a return r # Comprobación de equivalencia de dispersaAdensa # ============================================== # normalDispersa(ps) es la representación dispersa de un polinomio. def normalDispersa(ps: list[tuple[int, A]]) -> list[tuple[int, A]]: xs = sorted(list({p[0] for p in ps}), reverse=True) ys = [p[1] for p in ps] return [(x, y) for (x, y) in zip(xs, ys) if y != 0] # dispersaAleatoria() genera representaciones densas de polinomios # aleatorios. Por ejemplo, # >>> dispersaAleatoria().example() # [(5, -6), (2, -1), (0, 2)] # >>> dispersaAleatoria().example() # [(6, -7)] # >>> dispersaAleatoria().example() # [(7, 2), (4, 9), (3, 3), (0, -2)] def dispersaAleatoria() -> st.SearchStrategy[list[tuple[int, int]]]: return st.lists(st.tuples(st.integers(min_value=0, max_value=9), st.integers(min_value=-9, max_value=9)))\ .map(normalDispersa) # La propiedad es @given(ps=dispersaAleatoria()) def test_dispersaAdensa(ps: list[tuple[int, int]]) -> None: r = dispersaAdensa(ps) assert dispersaAdensa2(ps) == r assert dispersaAdensa3(ps) == r # Propiedad # ========= # La primera propiedad es @given(xs=densaAleatoria()) def test_dispersaAdensa_densaAdispersa(xs: list[int]) -> None: assert dispersaAdensa(densaAdispersa(xs)) == xs # La segunda propiedad es @given(ps=dispersaAleatoria()) def test_densaAdispersa_dispersaAdensa(ps: list[tuple[int, int]]) -> None: assert densaAdispersa(dispersaAdensa(ps)) == ps # La comprobación es # > poetry run pytest -v Polinomios_Transformaciones_dispersa_y_densa.py # test_densaADispersa PASSED # test_dispersaAdensa PASSED # test_dispersaAdensa_densaAdispersa PASSED # test_densaAdispersa_dispersaAdensa PASSED |