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.