// Copyright (c) 2003 Nick Mathewson.  See LICENSE for licensing information.
// $Id: comb.h 958 2003-12-11 11:07:51Z nickm $
// comb.h -- Basic combinatorics
#ifndef _COMB_H
#define _COMB_H

#include <assert.h>

// return n factorial.
inline long fact(int n) {
  assert(n>=0);
  int r = 1;
  for (int i = 2; i <= n; ++i) {
    r *= i;
  }
  return r;
}

// return the number of combinations of n items taken k at a time.
inline long comb(int n, int k) {
  /* COMB(n,k) = n!/(k!(n-k)!) */
  assert(n>=0 && k>=0 && k<=n);
  int t = n-k;
  if (k>t) { int tmp = t; t = k; k = tmp; }
  int r = 1;
  for (int i = t+1; i <= n; ++i) {
    r *= i;
  }
  for (int i = 2; i <= k; ++i) {
    r /= i;
  }
  return r;
}

// return the number of ways to place n identical items into k distinct bins.
inline long bins(int n, int k) {
  return comb(n+k-1, k-1);
}

#endif