{"id":8038,"date":"2023-04-18T06:00:03","date_gmt":"2023-04-18T04:00:03","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8038"},"modified":"2023-04-13T18:52:30","modified_gmt":"2023-04-13T16:52:30","slug":"18-abr-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/18-abr-23\/","title":{"rendered":"TAD de los polinomios: Transformaciones entre las representaciones dispersa y densa"},"content":{"rendered":"<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   densaAdispersa :: (Num a, Eq a) => [a] -> [(Int,a)]\n   dispersaAdensa :: (Num a, Eq a) => [(Int,a)] -> [a]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>densaAdispersa xs<\/code> es la representaci\u00f3n dispersa del polinomio cuya representaci\u00f3n densa es <code>xs<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> densaAdispersa [9,0,0,5,0,4,7]\n     [(6,9),(3,5),(1,4),(0,7)]\n<\/pre>\n<ul>\n<li><code>dispersaAdensa ps<\/code> es la representaci\u00f3n densa del polinomio cuya representaci\u00f3n dispersa es <code>ps<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> dispersaAdensa [(6,9),(3,5),(1,4),(0,7)]\n     [9,0,0,5,0,4,7]\n<\/pre>\n<p>Comprobar con QuickCheck que las funciones densaAdispersa y dispersaAdensa son inversas.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Data.List (nub, sort)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n de densaAdispersa\n-- ===============================\n\ndensaAdispersa :: (Num a, Eq a) => [a] -> [(Int,a)]\ndensaAdispersa xs = [(m,a) | (m,a) <- zip [n-1,n-2..] xs, a \/= 0]\n  where n  = length xs\n\n-- 2\u00aa definici\u00f3n de densaAdispersa\n-- ===============================\n\ndensaAdispersa2 :: (Num a, Eq a) => [a] -> [(Int,a)]\ndensaAdispersa2 xs = reverse (aux (reverse xs) 0)\n  where aux [] _ = []\n        aux (0:ys) n = aux ys (n+1)\n        aux (y:ys) n = (n,y) : aux ys (n+1)\n\n-- Comprobaci\u00f3n de equivalencia de densaAdispersa\n-- ==============================================\n\n-- La propiedad es\nprop_densaAdispersa :: [Int] -> Bool\nprop_densaAdispersa xs =\n  densaAdispersa xs == densaAdispersa2 xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_densaAdispersa\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> densaAdispersa (5 : replicate (10^7) 0)\n--    [(10000000,5)]\n--    (4.54 secs, 3,280,572,504 bytes)\n--    \u03bb> densaAdispersa2 (5 : replicate (10^7) 0)\n--    [(10000000,5)]\n--    (7.35 secs, 3,696,968,576 bytes)\n\n-- 1\u00aa definici\u00f3n de dispersaAdensa\n-- ===============================\n\ndispersaAdensa :: (Num a, Eq a) => [(Int,a)] -> [a]\ndispersaAdensa []      = []\ndispersaAdensa [(n,a)] = a : replicate n 0\ndispersaAdensa ((n,a):(m,b):ps) =\n  a : replicate (n-m-1) 0 ++ dispersaAdensa ((m,b):ps)\n\n-- 2\u00aa definici\u00f3n de dispersaAdensa\n-- ===============================\n\ndispersaAdensa2 :: (Num a, Eq a) => [(Int,a)] -> [a]\ndispersaAdensa2 []           = []\ndispersaAdensa2 ps@((n,_):_) =\n  [coeficiente ps m | m <- [n,n-1..0]]\n\n-- (coeficiente ps n) es el coeficiente del t\u00e9rmino de grado n en el\n-- polinomio cuya representaci\u00f3n densa es ps. Por ejemplo,\n--    coeficiente [(6,9),(3,5),(1,4),(0,7)] 3  ==  5\n--    coeficiente [(6,9),(3,5),(1,4),(0,7)] 4  ==  0\ncoeficiente :: (Num a, Eq a) => [(Int,a)] -> Int -> a\ncoeficiente [] _                     = 0\ncoeficiente ((m,a):ps) n | n > m     = 0\n                         | n == m    = a\n                         | otherwise = coeficiente ps n\n\n-- Comprobaci\u00f3n de equivalencia de dispersaAdensa\n-- ==============================================\n\n-- Tipo de las representaciones dispersas de polinomios.\nnewtype Dispersa = Dis [(Int,Int)]\n  deriving Show\n\n-- dispersaArbitraria es un generador de representaciones dispersas de\n-- polinomios. Por ejemplo,\n--    \u03bb> sample dispersaArbitraria\n--    Dis []\n--    Dis []\n--    Dis [(3,-2),(2,0),(0,3)]\n--    Dis [(6,1),(4,-2),(3,4),(2,-4)]\n--    Dis []\n--    Dis [(5,-7)]\n--    Dis [(12,5),(11,-8),(10,3),(8,-10),(7,-5),(4,12),(3,6),(2,-8),(1,11)]\n--    Dis [(7,-2),(2,-8)]\n--    Dis [(14,-15)]\n--    Dis [(17,5),(16,1),(15,-1),(14,10),(13,5),(12,-15),(9,12),(6,14)]\n--    Dis [(19,17),(12,7),(8,-3),(7,13),(5,-2),(4,7)]\ndispersaArbitraria :: Gen Dispersa\ndispersaArbitraria = do\n  (xs, ys) <- arbitrary\n  let xs' = nub (reverse (sort (map abs xs)))\n      ys' = filter (\/= 0) ys\n  return (Dis (zip xs' ys'))\n\n-- Dispersa est\u00e1 contenida en Arbitrary\ninstance Arbitrary Dispersa where\n  arbitrary = dispersaArbitraria\n\n-- La propiedad es\nprop_dispersaAdensa :: Dispersa -> Bool\nprop_dispersaAdensa (Dis xs) =\n  dispersaAdensa xs == dispersaAdensa2 xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_dispersaAdensa\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia de dispersaAdensa\n-- ===========================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (dispersaAdensa [(10^7,5)])\n--    10000001\n--    (0.11 secs, 560,566,848 bytes)\n--    \u03bb> length (dispersaAdensa2 [(10^7,5)])\n--    10000001\n--    (2.51 secs, 2,160,567,112 bytes)\n\n-- Propiedad\n-- =========\n\n-- Tipo de las representaciones densas de polinomios.\nnewtype Densa = Den [Int]\n  deriving Show\n\n-- densaArbitraria es un generador de representaciones dispersas de\n-- polinomios. Por ejemplo,\n--    \u03bb> sample densaArbitraria\n--    Den []\n--    Den []\n--    Den []\n--    Den [-6,6,5,-3]\n--    Den []\n--    Den [8,-7,-10,8,-10,-4,10,6,10]\n--    Den [-6,2,11,-4,-9,-5,9,2,2,9]\n--    Den [-6,9,-2]\n--    Den [-1,-7,15,1,5,-2,13,16,8,7,2,16,-2,16,-7,4]\n--    Den [8,13,-4,-2,-10,3,5,-4,-6,13,-9,-12,8,11,9,-18,12,10]\n--    Den [-1,-2,11,17,-7,13,-12,-19,16,-10,-18,-19,1,-4,-17,10,1,10]\ndensaArbitraria :: Gen Densa\ndensaArbitraria = do\n  ys <- arbitrary\n  let ys' = dropWhile (== 0) ys\n  return (Den ys')\n\n-- Dispersa est\u00e1 contenida en Arbitrary\ninstance Arbitrary Densa where\n  arbitrary = densaArbitraria\n\n-- La primera propiedad es\nprop_dispersaAdensa_densaAdispersa :: Densa -> Bool\nprop_dispersaAdensa_densaAdispersa (Den xs) =\n  dispersaAdensa (densaAdispersa xs) == xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_dispersaAdensa_densaAdispersa\n--    +++ OK, passed 100 tests.\n\n-- La segunda propiedad es\nprop_densaAdispersa_dispersaAdensa :: Dispersa -> Bool\nprop_densaAdispersa_dispersaAdensa (Dis ps) =\n  densaAdispersa (dispersaAdensa ps) == ps\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_densaAdispersa_dispersaAdensa\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom itertools import dropwhile\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A', int, float, complex)\n\n# 1\u00aa definici\u00f3n de densaAdispersa\n# ===============================\n\ndef densaAdispersa(xs: list[A]) -> list[tuple[int, A]]:\n    n = len(xs)\n    return [(m, a) for (m, a) in zip(range(n-1, -1, -1),  xs) if a != 0]\n\n# 2\u00aa definici\u00f3n de densaAdispersa\n# ===============================\n\ndef densaAdispersa2(xs: list[A]) -> list[tuple[int, A]]:\n    def aux(xs: list[A], n: int) -> list[tuple[int, A]]:\n        if not xs:\n            return []\n        if xs[0] == 0:\n            return aux(xs[1:], n + 1)\n        return [(n, xs[0])] + aux(xs[1:], n + 1)\n\n    return list(reversed(aux(list(reversed(xs)), 0)))\n\n# 3\u00aa definici\u00f3n de densaAdispersa\n# ===============================\n\ndef densaAdispersa3(xs: list[A]) -> list[tuple[int, A]]:\n    r = []\n    n = len(xs) - 1\n    for x in xs:\n        if x != 0:\n            r.append((n, x))\n        n -= 1\n    return r\n\n# Comprobaci\u00f3n de equivalencia de densaAdispersa\n# ==============================================\n\n# normalDensa(ps) es la representaci\u00f3n dispersa de un polinomio.\ndef normalDensa(xs: list[A]) -> list[A]:\n    return list(dropwhile(lambda x: x == 0, xs))\n\n# densaAleatoria() genera representaciones densas de polinomios\n# aleatorios. Por ejemplo,\n#    >>> densaAleatoria().example()\n#    [-5, 9, -6, -5, 7, -5, -1, 9]\n#    >>> densaAleatoria().example()\n#    [-4, 9, -3, -3, -5, 0, 6, -8, 8, 6, 0, -9]\n#    >>> densaAleatoria().example()\n#    [-3, -1, 2, 0, -9]\ndef densaAleatoria() -> st.SearchStrategy[list[int]]:\n    return st.lists(st.integers(min_value=-9, max_value=9))\\\n             .map(normalDensa)\n\n# La propiedad es\n@given(xs=densaAleatoria())\ndef test_densaADispersa(xs: list[int]) -> None:\n    r = densaAdispersa(xs)\n    assert densaAdispersa2(xs) == r\n    assert densaAdispersa3(xs) == r\n\n# 1\u00aa definici\u00f3n de dispersaAdensa\n# ===============================\n\ndef dispersaAdensa(ps: list[tuple[int, A]]) -> list[A]:\n    if not ps:\n        return []\n    if len(ps) == 1:\n        return [ps[0][1]] + [0] * ps[0][0]\n    (n, a) = ps[0]\n    (m, _) = ps[1]\n    return [a] + [0] * (n-m-1) + dispersaAdensa(ps[1:])\n\n# 2\u00aa definici\u00f3n de dispersaAdensa\n# ===============================\n\n# coeficiente(ps, n) es el coeficiente del t\u00e9rmino de grado n en el\n# polinomio cuya representaci\u00f3n densa es ps. Por ejemplo,\n#    coeficiente([(6, 9), (3, 5), (1, 4), (0, 7)], 3)  ==  5\n#    coeficiente([(6, 9), (3, 5), (1, 4), (0, 7)], 4)  ==  0\ndef coeficiente(ps: list[tuple[int, A]], n: int) -> A:\n    if not ps:\n        return 0\n    (m, a) = ps[0]\n    if n > m:\n        return 0\n    if n == m:\n        return a\n    return coeficiente(ps[1:], n)\n\ndef dispersaAdensa2(ps: list[tuple[int, A]]) -> list[A]:\n    if not ps:\n        return []\n    n = ps[0][0]\n    return [coeficiente(ps, m) for m in range(n, -1, -1)]\n\n# 3\u00aa definici\u00f3n de dispersaAdensa\n# ===============================\n\ndef dispersaAdensa3(ps: list[tuple[int, A]]) -> list[A]:\n    if not ps:\n        return []\n    n = ps[0][0]\n    r: list[A] = [0] * (n + 1)\n    for (m, a) in ps:\n        r[n-m] = a\n    return r\n\n# Comprobaci\u00f3n de equivalencia de dispersaAdensa\n# ==============================================\n\n# normalDispersa(ps) es la representaci\u00f3n dispersa de un polinomio.\ndef normalDispersa(ps: list[tuple[int, A]]) -> list[tuple[int, A]]:\n    xs = sorted(list({p[0] for p in ps}), reverse=True)\n    ys = [p[1] for p in ps]\n    return [(x, y) for (x, y) in zip(xs, ys) if y != 0]\n\n# dispersaAleatoria() genera representaciones densas de polinomios\n# aleatorios. Por ejemplo,\n#    >>> dispersaAleatoria().example()\n#    [(5, -6), (2, -1), (0, 2)]\n#    >>> dispersaAleatoria().example()\n#    [(6, -7)]\n#    >>> dispersaAleatoria().example()\n#    [(7, 2), (4, 9), (3, 3), (0, -2)]\ndef dispersaAleatoria() -> st.SearchStrategy[list[tuple[int, int]]]:\n    return st.lists(st.tuples(st.integers(min_value=0, max_value=9),\n                              st.integers(min_value=-9, max_value=9)))\\\n             .map(normalDispersa)\n\n# La propiedad es\n@given(ps=dispersaAleatoria())\ndef test_dispersaAdensa(ps: list[tuple[int, int]]) -> None:\n    r = dispersaAdensa(ps)\n    assert dispersaAdensa2(ps) == r\n    assert dispersaAdensa3(ps) == r\n\n# Propiedad\n# =========\n\n# La primera propiedad es\n@given(xs=densaAleatoria())\ndef test_dispersaAdensa_densaAdispersa(xs: list[int]) -> None:\n    assert dispersaAdensa(densaAdispersa(xs)) == xs\n\n# La segunda propiedad es\n@given(ps=dispersaAleatoria())\ndef test_densaAdispersa_dispersaAdensa(ps: list[tuple[int, int]]) -> None:\n    assert densaAdispersa(dispersaAdensa(ps)) == ps\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -v Polinomios_Transformaciones_dispersa_y_densa.py\n#    test_densaADispersa PASSED\n#    test_dispersaAdensa PASSED\n#    test_dispersaAdensa_densaAdispersa PASSED\n#    test_densaAdispersa_dispersaAdensa PASSED\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir las funciones densaAdispersa :: (Num a, Eq a) => [a] -> [(Int,a)] dispersaAdensa :: (Num a, Eq a) => [(Int,a)] -> [a] tales que densaAdispersa xs es la representaci\u00f3n dispersa del polinomio cuya representaci\u00f3n densa es xs. Por ejemplo, \u03bb> densaAdispersa [9,0,0,5,0,4,7] [(6,9),(3,5),(1,4),(0,7)] dispersaAdensa ps es la representaci\u00f3n densa del polinomio cuya representaci\u00f3n dispersa&#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":[581],"tags":[265],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8038"}],"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=8038"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8038\/revisions"}],"predecessor-version":[{"id":8048,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8038\/revisions\/8048"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8038"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8038"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8038"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}