大数置换nPr的最佳程序

Question

我对编程是个新手，并且一直被困在置换部分。我有工作的代码，大数字的组合，这是存储在矩阵中，但我不能找到我应该改变什么，以获得结果。我尝试了递归方法来进行排列，但不能快速得到结果。

这是我得到的组合代码，我应该做什么条件的改变，才能得到排列？

 void combination()
 {
   int i,j;
   for(i=0;i<100;i++)
   {
     nCr[i][0]=1;
     nCr[i][i]=1;
   }
   for(i=1;i<100;i++)
     for(j=1;j<100;j++)
        if (i!=j)
        {
          nCr[i][j] = (nCr[i-1][j] + nCr[i-1][j-1]);
        }
 }

Answer 1

排列的递归规则可以很容易地从定义中推导出来：

nPk = n*(n-1)*(n-2)* ... * (n-k+1) = n * (n-1)P(k-1)

转换为代码：

for(i=0;i<100;i++)
{
  nPr[i][0]=1;
}
for(i=1;i<100;i++)
  for(j=1;j<100;j++)
     if (i!=j)
     {
       nPr[i][j] = i * nPr[i-1][j-1];
     }

注意，排列的数量增长很快，并且溢出了可用于int的存储:例如，13P11已经超出了带符号的32位整数的范围。

Answer 2

您可以使用下面的伪代码来计算排列和组合，因为mod总是一个非常大的素数。

对于置换nPr

func permutation(r,n,mod):
    q=factorial(n) // you should precompute them and saved in an array for a better execution time  
    r=(factorial(r))%mod
    return (q*math.pow(r,mod-2))%mod

对于组合nCr

func combination(r,n,mod):
    q=factorial(n)  
    r=(factorial(r)*factorial(n-r))%mod
    return (q*math.pow(r,mod-2))%mod

你应该预先计算阶乘，以获得良好的执行时间。

fact[100000]
fact[0]=fact[1]=1
func factorial_compute():
    for x from 2 to 100000:
        fact[x]=(x*fact[x-1])%mod

因此阶乘函数将是

func factorial(x):
    return(fact[x])

有关这方面的数学参考：http://mathworld.wolfram.com/ModularInverse.html