0

我是编程新手，被困在排列部分。我有代码可用于组合存储在矩阵中的大数，但我无法找到我应该改变什么以获得结果。我尝试了排列的递归方法，但无法获得快速的结果。

这是我得到的组合代码我应该在这里做什么来获得排列的条件变化？

 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]);
        }
 }
4

2 回答 2

1

A recurrence rule for permutations can be easily derived from the definition:

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

Converted to code:

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];
     }

Note that the number of permutations grows fast and overflows the storage available for int: 13P11 for example is already out of range with signed 32bit integers.

于 2013-11-08T19:09:47.457 回答
0

好吧，鉴于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

于 2014-04-20T14:42:14.673 回答