{"id":8283,"date":"2023-09-19T06:00:12","date_gmt":"2023-09-19T04:00:12","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8283"},"modified":"2024-05-17T18:47:30","modified_gmt":"2024-05-17T16:47:30","slug":"19-sep-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/19-sep-23\/","title":{"rendered":"Coeficientes binomiales (con programaci\u00f3n din\u00e1mica)"},"content":{"rendered":"<p>El coeficiente binomial <code>n<\/code> sobre <code>k<\/code> es el n\u00famero de subconjuntos de <code>k<\/code> elementos escogidos de un conjunto con <code>n<\/code> elementos.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   binomial :: Integer -> Integer -> Integer\n<\/pre>\n<p>tal que <code>binomial n k<\/code> es el coeficiente binomial <code>n<\/code> sobre <code>k<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   binomial 6 3 == 20\n   binomial 5 2 == 10\n   binomial 5 3 == 10\n<\/pre>\n<p><!--more--><\/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\">\nmodule Coeficientes_binomiales where\n\nimport Data.Array (Array, (!), array)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\nbinomial1 :: Integer -> Integer -> Integer\nbinomial1 _ 0 = 1\nbinomial1 n k\n  | n == k    = 1\n  | otherwise = binomial1 (n-1) (k-1) + binomial1 (n-1) k\n\n-- 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nbinomial2 :: Integer -> Integer -> Integer\nbinomial2 n k = matrizBinomial2 n k ! (n,k)\n\n-- (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el\n-- valor en la posici\u00f3n (i,j) (con j <= i) es el coeficiente binomial i\n-- sobre j. Por ejemplo,\n--    \u03bb> [[(matrizBinomial2 3 3)!(i,j) | j <- [0..i]] | i <- [0..3]]\n--    [[1],[1,1],[1,2,1],[1,3,3,1]]\nmatrizBinomial2 :: Integer -> Integer -> Array (Integer,Integer) Integer\nmatrizBinomial2 n k = q where\n  q = array ((0,0),(n,k)) [((i,j),f i j) | i <- [0..n], j <- [0..k]]\n  f _ 0 = 1\n  f i j\n    | i == j    = 1\n    | otherwise = q!(i-1,j-1) + q!(i-1,j)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> binomial1 25 12\n--    5200300\n--    (6.45 secs, 2,654,797,776 bytes)\n--    \u03bb> binomial2 25 12\n--    5200300\n--    (0.00 secs, 826,272 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    binomial1 6 3 `shouldBe` 20\n  it \"e2\" $\n    binomial1 5 2 `shouldBe` 10\n  it \"e3\" $\n    binomial1 5 3 `shouldBe` 10\n  it \"e4\" $\n    binomial2 6 3 `shouldBe` 20\n  it \"e5\" $\n    binomial2 5 2 `shouldBe` 10\n  it \"e6\" $\n    binomial2 5 3 `shouldBe` 10\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--\n--    Finished in 0.0006 seconds\n--    6 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nimport numpy as np\nimport numpy.typing as npt\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa definici\u00f3n (por recursi\u00f3n)\n# =============================\n\ndef binomial1(n: int, k: int) -> int:\n    if k == 0:\n        return 1\n    if n == k:\n        return 1\n    return binomial1(n-1, k-1) + binomial1(n-1, k)\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =========================================\n\ndef binomial2(n: int, k: int) -> int:\n    return matrizBinomial2(n, k)[n][k]\n\n# (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el\n# valor en la posici\u00f3n (i,j) (con j <= i) es el coeficiente binomial i\n# sobre j. Por ejemplo,\n#    >>> matrizBinomial2(3, 3)\n#    [[1, 0, 0, 0], [1, 1, 0, 0], [1, 2, 1, 0], [1, 3, 3, 1]]\ndef matrizBinomial2(n: int, k: int) -> list[list[int]]:\n    q = [[0 for i in range(k + 1)] for j in range(n + 1)]\n\n    for i in range(n + 1):\n        for j in range(min(i, k) + 1):\n            if j == 0:\n                q[i][j] = 1\n            elif i == j:\n                q[i][j] = 1\n            else:\n                q[i][j] = q[i - 1][j - 1] + q[i - 1][j]\n\n    return q\n\n# 3\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica y numpy)\n# ================================================\n\ndef binomial3(n: int, k: int) -> int:\n    return matrizBinomial3(n, k)[n][k]\n\n# (matrizBinomial3 n k) es la matriz de orden (n+1)x(k+1) tal que el\n# valor en la posici\u00f3n (i,j) (con j <= i) es el coeficiente binomial i\n# sobre j. Por ejemplo,\n#    >>> matrizBinomial3(3, 3)\n#    array([[1, 0, 0, 0],\n#           [1, 1, 0, 0],\n#           [1, 2, 1, 0],\n#           [1, 3, 3, 1]])\ndef matrizBinomial3(n: int, k: int) -> npt.NDArray[np.int_]:\n    q = np.zeros((n + 1, k + 1), dtype=object)\n\n    for i in range(n + 1):\n        for j in range(min(i, k) + 1):\n            if j == 0:\n                q[i, j] = 1\n            elif i == j:\n                q[i, j] = 1\n            else:\n                q[i, j] = q[i - 1, j - 1] + q[i - 1, j]\n\n    return q\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('binomial1(27, 12)')\n#    4.26 segundos\n#    >>> tiempo('binomial2(27, 12)')\n#    0.00 segundos\n#    >>> tiempo('binomial3(27, 12)')\n#    0.00 segundos\n#\n# >>> tiempo('binomial2(50000, 12)')\n# 0.18 segundos\n# >>> tiempo('binomial3(50000, 12)')\n# 0.26 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_binomial() -> None:\n    assert binomial1(6, 3) == 20\n    assert binomial1(5, 2) == 10\n    assert binomial1(5, 3) == 10\n    assert binomial2(6, 3) == 20\n    assert binomial2(5, 2) == 10\n    assert binomial2(5, 3) == 10\n    assert binomial3(6, 3) == 20\n    assert binomial3(5, 2) == 10\n    assert binomial3(5, 3) == 10\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_binomial()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El coeficiente binomial n sobre k es el n\u00famero de subconjuntos de k elementos escogidos de un conjunto con n elementos. Definir la funci\u00f3n binomial :: Integer -> Integer -> Integer tal que binomial n k es el coeficiente binomial n sobre k. Por ejemplo, binomial 6 3 == 20 binomial 5 2 == 10&#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":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8283"}],"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=8283"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8283\/revisions"}],"predecessor-version":[{"id":8578,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8283\/revisions\/8578"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8283"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8283"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8283"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}