Пресметување на комбинации

In combinatorial mathematics, a combination is an un-ordered collection of distinct elements, usually of a prescribed size and taken from a given set.

Овде ќе зборувам за алгоритам за пресметување на комбинации. Според основната дефиниција може да се направи една функција, но како што може да се забележи е многу неефикасна во смисла на тоа што n! тешко може да се смести во променлива, поради големината. На пример 15! = 1,307,674,368,000. Ова не го собира во long, а да не зборуваме за int. Ова не е единствениот недостаток на овој алгоритам, има премногу пресметки па дури и да го поправиме овој алгоритам. Има уште една работа освен комплексноста за која нема да зборувам овде. Еднаш при решавање на задача, го решив најголемиот дел на задачата, и кога дојде она "најлесното", пресметување на комбинациите го оптимизирав овој алгоритам и цело време ми паѓаше на време, се додека не ми текна на нешто што го знаев од часовите по математика. Потоа направив брз алгоритам, но ми беше криво што порано не сум се сетил на тоа :) Но од грешките се учи, па тоа ми беше една добра лекција, доколку некој алгоритам е точен, но паѓа на време, размисли дали проблемот може да се реши со друг алгоритам.

Решението на нашиот проблем лежи во Паскаловиот триаголник. Колку просто :)



Нема да објаснувам многу за ова, повеќе можете да прочитате на wikipedia.

Еве една инплементација на пресметување на комбинации со помош на Паскалов триаголник.

long N=20;
int i,j;
long comb[][] = new long[N][N];

for (j=0;j<N;j++) {
  comb[0][j]=1;
  comb[j][j]=1;
  for (i=1;i<j;i++) {
       comb[i][j]=comb[i-1][j-1]+comb[i][j-1];
  }
}

Како што се гледа, комплексноста на алгоритмот е O(N), а кога ни се пресметани "претходните" комбинации, пресметувањето на една комбинација е во константно време O(1). За да пресметаме N "последователни" комбинации ни треба O(N). Нема да навлегувам во понатамошни анализи :)