binomial :: Integer -> Integer -> Integer

   binomial 6 3 == 20
   binomial 5 2 == 10
   binomial 5 3 == 10

module Coeficientes_binomiales where

import Data.Array (Array, (!), array)
import Test.Hspec (Spec, hspec, it, shouldBe)

-- 1ª definición (por recursión)
-- =============================

binomial1 :: Integer -> Integer -> Integer
binomial1 _ 0 = 1
binomial1 n k
  | n == k    = 1
  | otherwise = binomial1 (n-1) (k-1) + binomial1 (n-1) k

-- 2ª definición (con programación dinámica)
-- =========================================

binomial2 :: Integer -> Integer -> Integer
binomial2 n k = matrizBinomial2 n k ! (n,k)

-- (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el
-- valor en la posición (i,j) (con j <= i) es el coeficiente binomial i
-- sobre j. Por ejemplo,
--    λ> [[(matrizBinomial2 3 3)!(i,j) | j <- [0..i]] | i <- [0..3]]
--    [[1],[1,1],[1,2,1],[1,3,3,1]]
matrizBinomial2 :: Integer -> Integer -> Array (Integer,Integer) Integer
matrizBinomial2 n k = q where
  q = array ((0,0),(n,k)) [((i,j),f i j) | i <- [0..n], j <- [0..k]]
  f _ 0 = 1
  f i j
    | i == j    = 1
    | otherwise = q!(i-1,j-1) + q!(i-1,j)

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> binomial1 25 12
--    5200300
--    (6.45 secs, 2,654,797,776 bytes)
--    λ> binomial2 25 12
--    5200300
--    (0.00 secs, 826,272 bytes)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    binomial1 6 3 `shouldBe` 20
  it "e2" $
    binomial1 5 2 `shouldBe` 10
  it "e3" $
    binomial1 5 3 `shouldBe` 10
  it "e4" $
    binomial2 6 3 `shouldBe` 20
  it "e5" $
    binomial2 5 2 `shouldBe` 10
  it "e6" $
    binomial2 5 3 `shouldBe` 10

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--
--    Finished in 0.0006 seconds
--    6 examples, 0 failures

from sys import setrecursionlimit
from timeit import Timer, default_timer

import numpy as np
import numpy.typing as npt

setrecursionlimit(10**6)

# 1ª definición (por recursión)
# =============================

def binomial1(n: int, k: int) -> int:
    if k == 0:
        return 1
    if n == k:
        return 1
    return binomial1(n-1, k-1) + binomial1(n-1, k)

# 2ª definición (con programación dinámica)
# =========================================

def binomial2(n: int, k: int) -> int:
    return matrizBinomial2(n, k)[n][k]

# (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el
# valor en la posición (i,j) (con j <= i) es el coeficiente binomial i
# sobre j. Por ejemplo,
#    >>> matrizBinomial2(3, 3)
#    [[1, 0, 0, 0], [1, 1, 0, 0], [1, 2, 1, 0], [1, 3, 3, 1]]
def matrizBinomial2(n: int, k: int) -> list[list[int]]:
    q = [[0 for i in range(k + 1)] for j in range(n + 1)]

    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            if j == 0:
                q[i][j] = 1
            elif i == j:
                q[i][j] = 1
            else:
                q[i][j] = q[i - 1][j - 1] + q[i - 1][j]

    return q

# 3ª definición (con programación dinámica y numpy)
# ================================================

def binomial3(n: int, k: int) -> int:
    return matrizBinomial3(n, k)[n][k]

# (matrizBinomial3 n k) es la matriz de orden (n+1)x(k+1) tal que el
# valor en la posición (i,j) (con j <= i) es el coeficiente binomial i
# sobre j. Por ejemplo,
#    >>> matrizBinomial3(3, 3)
#    array([[1, 0, 0, 0],
#           [1, 1, 0, 0],
#           [1, 2, 1, 0],
#           [1, 3, 3, 1]])
def matrizBinomial3(n: int, k: int) -> npt.NDArray[np.int_]:
    q = np.zeros((n + 1, k + 1), dtype=object)

    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            if j == 0:
                q[i, j] = 1
            elif i == j:
                q[i, j] = 1
            else:
                q[i, j] = q[i - 1, j - 1] + q[i - 1, j]

    return q

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('binomial1(27, 12)')
#    4.26 segundos
#    >>> tiempo('binomial2(27, 12)')
#    0.00 segundos
#    >>> tiempo('binomial3(27, 12)')
#    0.00 segundos
#
# >>> tiempo('binomial2(50000, 12)')
# 0.18 segundos
# >>> tiempo('binomial3(50000, 12)')
# 0.26 segundos

# Verificación
# ============

def test_binomial() -> None:
    assert binomial1(6, 3) == 20
    assert binomial1(5, 2) == 10
    assert binomial1(5, 3) == 10
    assert binomial2(6, 3) == 20
    assert binomial2(5, 2) == 10
    assert binomial2(5, 3) == 10
    assert binomial3(6, 3) == 20
    assert binomial3(5, 2) == 10
    assert binomial3(5, 3) == 10
    print("Verificado")

# La verificación es
#    >>> test_binomial()
#    Verificado