Most efficient way to calculation permutation P(n,

问题:

If n can be as large as 1M and r something like 100, then what is the most efficient way to calculate nPr.

回答1:

P(n,r) = n! / (n-r)!

We easily can remove (n-r)! from nominator and denominator. Now formula is

P(n,r) = n*(n-1)*..(n-r+1)

.

.

.

Old answer, not for this question, about combinations:

C(n,k) = n! / (k! * (n-k)!)

We easily can remove (n-k)! from nominator and denominator. Now formula is

C(n,k) = n*(n-1)*..(n-k+1) / k! = n*(n-1)*..(n-k+1) / (1 * 2 * ...*k)

If we first calculate full nominator, it will very big.

But we can alternate steps - take n, then divide by the first term of denominator (1), multiplication by (n-1) - division by the second denominator term (2) and so on.

 C(n,k) = n / 1 * (n-1) / 2 * (n-2) / 3 .. * (n-k+1) / k

Note that partial nominator product always i divisible by partial denominator product of the same length.

With this approach intermediate result is not very big, and calculations with big numbers (long arithmetics) will be faster.