/*
* 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)));
}