nPr e nCr

Escreva uma função que calcule eficientemente nPr (o número de permutações de r itens de um conjunto de tamanho n) e outra função que calcule eficientemente nCr (o número de combinações de r itens de um conjunto de tamanho n, independentemente da ordem).

• A fórmula para calcular nPr é n!/(n-r)! ("!" é a operação fatorial).
• A fórmula para calcular nCr é n!/(r!(n-r)!).

Suas funções devem funcionar eficientemente em casos em que n! ou r! sejam muito grandes em comparação com o resultado. Calcular simplesmente os fatoriais e fazer a divisão fará seu programa estourar o tempo limite. Veja se consegue pensar em um método mais eficiente.

Exemplos

# Permutations

nPr(7, 4) ➞ 840
nPr(300, 3) ➞ 26730600

# Combinations

nCr(7, 4) ➞ 35
nCr(300, 3) ➞ 4455100
nCr(300, 297) ➞ 4455100

Observações

• n e r sempre serão inteiros positivos em que n >= r.
• Pense em quais fatores serão cancelados ao dividir os fatoriais.