# #############
# Combinations
# #############
#
# ..  contents::
#
# Definition
# ==========
#
# For some deeper statistical calculations,
# we need the number of combinations of *n* things
# taken *k* at a time, :math:`\binom{n}{k}`.
#
# ..  math::
#
#     \binom{n}{k} = \dfrac{n!}{k!(n-k)!}
#
# The function will use an internal ``fact()`` function because
# we don't need factorial anywhere else in the application.
#
# We'll rely on a simplistic factorial function without memoization.
#
# Test Case
# =========
#
# Here are two simple unit tests for this function provided
# as doctest examples.
#
# >>> from combo import combinations
# >>> combinations(4,2)
# 6
# >>> combinations(8,4)
# 70
#
# Implementation
# ===============
#
# Here's the essential function definition, with docstring:
# ::

def combinations(n: int, k: int) -> int:
    """Compute :math:`\binom{n}{k}`, the number of
    combinations of *n* things taken *k* at a time.

    :param n: integer size of population
    :param k: groups within the population
    :returns: :math:`\binom{n}{k}`
    """

# An important consideration here is that someone hasn't confused
# the two argument values.
# ::

    assert k <= n

# Here's the embedded factorial function. It's recursive. The Python
# stack limit is a limitation on the size of numbers we can use.
# ::

    def fact(a: int) -> int:
        if a == 0: return 1
        return a*fact(a-1)

# Here's the final calculation. Note that we're using integer division.
# Otherwise, we'd get an unexpected conversion to float.
# ::

    return fact(n)//(fact(k)*fact(n-k))

# We can make this more efficient by treating the factorial product
# as a *Multiset* of individual integer values. The product updates the
# multiset. The division removes items from the multiset. Once the final
# set of factors is available, the final product can be computed more efficiently.
