Calculate the number of combination of n things taken k at a time without repetition. #recursion #dynamic_programming #DPfCI

combination.cpp

// Combination(n, k):
//   Returns the number of combination of n things taken k
//   at a time without repetition.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

#undef RECURSION
#undef MEMOIZATION
#undef DYNAMIC_PROGRAMMING
#undef RUN

#define RECURSION 1
#define MEMOIZATION 2
#define DYNAMIC_PROGRAMMING 3
// #define RUN RECURSION
// #define RUN MEMOIZATION
#define RUN DYNAMIC_PROGRAMMING

// Helper
void Print(std::vector< std::vector<unsigned int> >& c)
{
  for (unsigned int i = 0 ; i < c.size() ; ++i) {
    for (unsigned int j = 0 ; j < c[i].size() ; ++j) {
      std::cout << c[i][j] << " ";
    }
    std::cout << std::endl;
  }
}

#if RUN == RECURSION

unsigned int
Combination(unsigned int n, unsigned int k)
{
  assert(n >= k);

  if (n == k || k == 0) {
    return 1;
  }/* else if (k == 1) {
    return n;
  }*/

  return Combination(n-1, k-1) + Combination(n-1, k);
}

#elif RUN == MEMOIZATION

unsigned int
Combination(unsigned int n, unsigned int k,
            std::vector< std::vector<unsigned int> >& memo)
{
  assert(n >= k);

  if (memo[n][k]) {
    return memo[n][k];
  }

  if (n == k || k == 0) {
    memo[n][k] = 1;
  }/* else if (k == 1) {
    memo[n][k] = n;
  }*/ else {
    memo[n][k] = Combination(n-1, k-1, memo) + Combination(n-1, k, memo);
  }

  return memo[n][k];
}

unsigned int
Combination(unsigned int n, unsigned int k)
{
  assert(n >= k);

  // C(n, k) = C(n, n-k), so we calculate this by C(n, min(k, n-k))
  k = std::min(k, n-k);
  // if (n - k < k) {
  //   k = n - k;
  // }

  // Define C(n, k) = comb[n][k].
  std::vector< std::vector<unsigned int> >
    memo(n+1, std::vector<unsigned int>(k+1, 0));

  return Combination(n, k, memo);
}

#elif RUN == DYNAMIC_PROGRAMMING

// unsigned int
// Combination(unsigned int n, unsigned int k)
// {
//   assert(n >= k);

//   // C(n, k) = C(n, n-k), so we calculate this by C(n, min(k, n-k))
//   k = std::min(k, n-k);
//   // if (n - k < k) {
//   //   k = n - k;
//   // }

//   // Define C(n, k) = comb[n][k].
//   std::vector< std::vector<unsigned int> >
//     comb(n+1, std::vector<unsigned int>(k+1, 0));

//   for (unsigned int i = 0 ; i <= n-k ; ++i) {
//     comb[i][0] = 1;
//   }
//   for (unsigned int i = 1 ; i <= k ; ++i) {
//     comb[i][i] = 1;
//   }

//   for (unsigned int i = 2 ; i <= n ; ++i) {
//     for (unsigned int j = (i > n-k) ? i - (n-k) : 1 ; j <= k ; ++j) {
//       comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
//     }
//   }

//   for (unsigned int i = 0 ; i < comb.size() ; ++i) {
//     for (unsigned int j = 0 ; j < comb[i].size() ; ++j) {
//       std::cout << comb[i][j] << " ";
//     }
//     std::cout << std::endl;
//   }
//   std::cout << std::endl;

//   return comb[n][k];
// }

unsigned int
Combination(unsigned int n, unsigned int k)
{
  assert(n >= k);

  // C(n, k) = C(n, n-k), so we calculate this by C(n, min(k, n-k))
  k = std::min(k, n-k);
  // if (n - k < k) {
  //   k = n - k;
  // }

  // Define C(n, k) = comb[n][k].
  std::vector< std::vector<unsigned int> >
    comb(n+1, std::vector<unsigned int>(k+1, 0));

  for (unsigned int i = 0 ; i <= n-k ; ++i) {
    comb[i][0] = 1;
  }
  for (unsigned int i = 1 ; i <= k ; ++i) {
    comb[i][i] = 1;
  }

  for (unsigned int j = 1 ; j <= k ; ++j) {
    for (unsigned int i = j + 1 ; i <= j + n-k ; ++i) {
      comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
    }
  }

  return comb[n][k];
}

// unsigned int
// Combination(unsigned int n, unsigned int k)
// {
//   assert(n >= k);

//   // C(n, k) = C(n, n-k), so we calculate this by C(n, min(k, n-k))
//   k = std::min(k, n-k);
//   // if (n - k < k) {
//   //   k = n - k;
//   // }

//   // Define C(n, k) = comb[k][n].
//   std::vector< std::vector<unsigned int> >
//     comb(k+1, std::vector<unsigned int>(n+1, 0));

//   for (unsigned int i = 0 ; i <= n-k ; ++i) {
//     comb[0][i] = 1;
//   }
//   for(unsigned int i = 0 ; i <= k ; ++i) {
//     comb[i][i] = 1;
//   }

//   for (unsigned int i = 1 ; i <= k ; ++i) {
//     for (unsigned int j = i + 1 ; j <= i + n-k ; ++j) {
//       comb[i][j] = comb[i][j-1] + comb[i-1][j-1];
//     }
//   }

//   return comb[k][n];
// }

#else // By math

// unsigned int Fractorial(unsigned int n)
// {
//   unsigned int f = 1;
//   for (unsigned int i = 1 ; i <= n ; ++i) {
//     f *= i;
//   }
//   return f;
// }

unsigned int
Combination(unsigned int n, unsigned int k)
{
  assert(n >= k);
  // return Fractorial(n) / (Fractorial(k) * Fractorial(n-k));

  // C(n, k) = C(n, n-k), so we calculate this by C(n, min(k, n-k))
  k = std::min(k, n - k);
  // if (n - k < k) {
  //   k = n - k;
  // }

  unsigned int x = 1, y = 1;
  for (; k ; --k, --n) {
    x *= n;
    y *= k;
  }

  assert(x >= y);
  return x / y;
}

#endif

int main()
{
  unsigned int n = 0, k = 0;
  std::cout << "Enter C(n, k): ";
  while (!(std::cin >> n >> k) || n < k) {
    std::cout << "Invalid input! Enter again: ";
    std::cin.clear();
  }
  std::cout << Combination(n, k) << std::endl;
  return 0;
}