Combinationを巡る冒険

組合せの計算はすぐに桁あふれするという。
それは、愚直に factorial(n) = n! を実装するからだと思う。
組合せcombination(n,r) = n ! (n -r +1)!/ r!にはfactorialの積がでてくるしね。

でも、ちょっとまった。組み合わせの計算をするときは、そんなふうに計算したかな？こうかな？

combination(5,2) = (5*4)/(2*1)

この式をいろいろと見ていると、

combination(5,2) = (((1*5)/1)*4)/2

と計算できることがわかる。

combination(n,r) = 1 * (n) / (1) * (n-1) / (2) ... * (n-r+1) / (r)

この式を左結合としてみてほしい。

そう、必要な計算だけにしぼってみたら、うまく桁あがりが抑えられる。交互に積、除を繰り返すのがポイントだ。しかもこの順番ですると割り算はかならず、割り切れる。

あとは、そう、combination(n,r) = combination(n,n-r)を使えば、無駄な計算が抑えられるはずだ。

#include <stdio.h>
#include <stdlib.h>
#define COMBUNDEF 0

unsigned long long combination( int n, int r);

unsigned long long combination( int n, int r){
  int i;
  unsigned long long work = 1;

  if( (n < r) || (n < 0) || (r < 0)){
    return COMBUNDEF;
  }
  
  for( i = 0; i < r; i++){
    work = work * (unsigned long long) (n - i);
    work = work / (unsigned long long) (i + 1);
  }

  return work;
}

/* driver for combination */
int main(void){
  int i, j;
  unsigned long long res;
  for(i=1;i<20;i++){
    for(j=0;j<=i;j++){
      res = combination( i, j);
      printf("%d,%d %llu\n",i, j, res); 
    }
  }

  exit(0);
}