计算置换P(n，r)的最有效方法，其中n可以是一个大整数 [英] Most efficient way to calculation permutation P(n,r) where n can be a large integer

问题描述

如果n可以大到1M，r大约是100，那么什么是最有效的计算nPr的方法.

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

推荐答案

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

我们可以轻松移除(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)!)

我们可以轻松移除(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.

但是我们可以选择其他步骤-取n，然后除以分母(1)的第一项，乘以(n-1)-除以第二分母项(2)，依此类推.

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.

这篇关于计算置换P(n，r)的最有效方法，其中n可以是一个大整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！