/*
 * choose.c
 * This program reads a set size and a sub-set size, and returns the 
 * number of different sub-sets that can be chosen from the set.
 */

#include <stdio.h>

/* Prototypes: */
int fact (int n);
int choose (int n, int k);

int main ()
{
  int   set_size;
  int   sub_set_size;
  
  /* Read the input. */
  printf ("Please enter the set size: ");
  scanf ("%d", &set_size);

  printf ("Please enter the sub-set size: ");
  scanf ("%d", &sub_set_size);

  /* Check the input. */
  if (set_size < 0 || sub_set_size < 0)
  {
    printf ("Illegal input!\n");
    return (1);
  }

  /* Compute the result. */
  printf ("There are %d possible sub-set(s) to choose.\n", 
          choose (set_size, sub_set_size));

  return (0);
}

/* ------------------------------------------------------------------------
 * Function: fact
 * Purpose : Compute the factorial of a non-negative number.
 * Input   : n - A non-negative number.
 * Returns : The factorial of n (n!).
 */
int fact (int n)
{
  int   res = 1;
  int   i;

  for (i = 1; i <= n; i++)
    res *= i;

  return (res);
}

/* ------------------------------------------------------------------------
 * Function: choose
 * Purpose : Compute (n over k), which is the number of possible different 
 *           sub-sets of size k one can choose from a set of size n.
 * Input   : n - The set size.
 *           k - The sub-set size.
 * Returns : (n over k).
 */
int choose (int n, int k)
{
  if (k > n)
    /* It is impossible to choose k > n out of n: */
    return (0);

  /*                                    n!
   * Use the formula:   n over k = -------------
   *                                k! * (n-k)!
   */
  return (fact(n) / (fact(k) * fact(n-k)));
}