Лучшая программа для перестановки nPr больших чисел

Я новичок в программировании и застрял в части перестановки. У меня есть код, который работает для комбинации больших чисел, который хранится в матрице, но я не могу найти, что мне следует изменить, чтобы получить результат. Я попробовал рекурсивный метод для перестановок, но не смог добиться быстрых результатов.Лучшая программа для перестановки nPr больших чисел

Это код, который я получил для комбинации, какое должно быть изменение в состоянии, которое я должен сделать здесь, чтобы получить перестановки?

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

источник

2013-11-08 user2970118

Что вы пытаетесь вычислить? Моя математика на этом немного ржавая, но не так ли, если вы ищете nCr, который является 'nCr [n] [r]' где 'n' и' r' - это значения, которые вы ищете. –

, если вы могли бы предоставить точное определение допустимости nPr больших чисел, чтобы было ясно, что именно пытается ваша программа. –

Я сниму свой ответ на комментарий: в любом случае nPk (n, k) или nCk (n, k) функция определена только для 0 <= k <= n. –

Правило повторения для перестановок может быть легко получено из определения:

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-битных целых чисел.

источник

2013-11-08 19:09:47 Joni

@ Аки, мы говорим о перестановках, а не о комбинациях. 13P11 - 3.113.510.400> 2^31. – Joni

ну, вы можете использовать следующий псевдокод для вычисления перестановки и комбинации, учитывая, что 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-20 14:42:14

Лучшая программа для перестановки nPr больших чисел

ответ

Смежные вопросы