Week 4 Exercises: combinations and permutations

Comments and questions to John Rowe.

The exercises use the example of permutations and combinations to illustrate two things. First, functions often call other functions and the "outer" functions can often be extremely simple. Second: requirements change and it's quite common to extend an existing function to handle a more complicated case. if the more-complicated function requires more arguments than the original it can sometimes be a good idea to have a "wrapper" function with the original name and arguments that just calls the more-complicated function. (Whether this is a good idea or not depends on your program: is the original, simpler function still required or should you just go through your code adding an extra argument? It's a judgement call.)

Exercises

1. Take your "factorial" code from last week. Recal that your code failed above 12! due the range integer values can take.

   We can get round this by declaring the reult to be of type long long (which is an optional extension to the C language which may generate a warning) which on our system uses 8 bytes for an integer, not 4. We can print long long variables using the "%lld" format.

   Make your "factorial" code into a function. Make sure it has a sensible name and a clear and unambigous comment. Put a prototype for the function in the appropriate place. Your function must return the value of the factorial to the calling function, to allow you to write statements such as:

     long long myfact;
     
     myfact = factorial(20);
   

   (assuming you have named your function "factorial"). The printf() statement is no longer required inside your factorial function although you may wish to keep it there for testing and debugging (see below).

   Negative factorials are not defined. One option to deal with this would be to make the argument an unsigned int. Another is to return a suitable value (I would suggest -1) and print a warning message.

   Modify your function to do the latter. Now add test/debug printf() statements inside your function to print out its argument and the value it is about to return. Have main() call it several times to thoroughly test it.

   Hand in the program and the test output. The demonstrator will be looking to be able to show that you have not tested it thoroughly. Don't let him/her succeed!

    

2. Revise the definition of cominations and permutations: ways of choosing r items from a choice of n (nPr and nCr). Read the following paragraphs carefully before starting to program.

   We are going to need an "nPr" function and a factorial function to calculate nCr. nPr could be calculated by dividing two factorials but this has problems with, say, 52P5 which is quite a sensible number but would require the division of two very large factorials.

   A better option would be to modify our factorial function to accept two arguments. Since we will need two functions (permutation and factorial), one option is to copy-and-paste the factorial function and modify the copy. The other is create a "wrapper" factorial function that just calls the permutation function with both arguments the same (since nPn == n!). The new, short function would look like:

   /*
    * Sensible comment here (same comment as before)
    */
   long long factorial(int n) {
     return my_permutation_function_name(n, n);
   }
   

   (Obviously I don't suggest that particular function name for your permuation function!)

   This is a fairly common situation: you have a simple function, you then need to create a more general one but it's still useful to be able to call the simpler one. The "wrapper" function can often be quite a good solution as you only need to write the guts of the code once.

   The easiest way to achieve this is to "break" your factorial function after the opening "{", finish off the new factorial function as above. This then leaves the body of your original factorial function as the basis for your permutation function.

   Using the above advice, extend your code to have two functions: a permuation and a factorial.

   Make sure your permuation function has appropriate checks for bad values.

   Add a combination function. The combination function will be extremely simple as it will just call the other two.

   Use your program to calculate your chances of winning the National Lottery (assuming you buy a ticket!), i.e. choosing the correct combination of six numbers from the choice 1 to 49.

   At the start of next week's session hand in your code and output for feedback. Tis week's work is not assessed.