Part I: Combinatorics
The first part of this homework assignment will have you write a few basic functions used widely in combinatorics.
1. Create a new project (called, for example, "homework05"), for this assignment. Do not use spaces in the name. Follow the same process as you did in the first assignment; if you need a refresher, please refer back to Homework 1.
2. Open the "main.cpp" file in your project and delete everything in it.
3. Make sure that you include and toss in a using namespace std.
4. Write an empty main() function. Remember the int return type, and go ahead and have it return 0 at the end so you don't forget it later.
5. The first function that you will define is called factorial, which will compute the mathematical factorial function. (Reminder: the factorial of a non-negative n is written n! and is equal to 1 * 2 * ... all the way up to ... * n. A special case is 0!, which by definition equals 1.)
The factorial function will take a single int parameter by value, and return an int. Write the prototype (declaration) of this function above main. Make sure you use the name factorial exactly, all lowercase. Below main, write the definition of this function. Use a for loop to compute the product of all of the integers from 1 up to and including the argument. You can assume that the argument will be greater than or equal to 0. If you get stuck, take a look at the sum function snippet that I did in class; the two functions are very similar.
6. Test your function by writing a couple cout statements in main that call it. For example, factorial(5)should return 120. Make sure that you try "edge cases", like factorial(0), to make sure it works correctly. Compile and run your code with those tests to see whether it works. If it doesn't, go back and try to figure out what you did wrong.
Be careful about testing it with large numbers; the factorial function grows very rapidly, and will overflow a regular integer around factorial(13). We could address this, but it's not critical for this particular assignment, so move on.
7. Next, we'll compute the number of permutations of a set of objects by using the factorial function we just wrote. (A permutation is a selection of objects where order matters. For example, if a set contains the 4 elements A, B, C, D, then ABC would be one permutation of 3 elements and BAC would be a different one.) So, declare and define a function named permutations that takes two ints by value, n and k, in that order. This function should return the number of possible permutations of k objects selected from a set of n total objects, computed by the following algorithm:
If k > n, the number of permutations is defined to be 0 (you can't choose more objects than the set contains). Otherwise, the formula for computing the number of permutations of k objects selected from a set of n objects is:
n!/(n-k)!
Use your factorial function to write the formula above to compute the number of permutations.
8. Test your permutations function in main just like you did the factorial function. As an example, how many permutations are there when you have a set of 4 objects and choose 2? Think about it and see if you can come up with the answer on your own, then compare your answer to the result generated by your function. Also try some edge cases, like when k > n or when one of the values is 0.
9. Next, write a function named combinations that takes two ints by value, n and k, in that order, and returns the number of possible combinations of k objects selected from a set of n total objects. (A combination is a selection of objects where order does not matter. For
example, if a set contains the 4 elements A, B, C, D, then you might only count ABC but not BCA, CBA, and so on.)
If k > n, the number of combinations is defined to be 0 (you can't choose more objects than the set contains).Otherwise, the formula for computing the number of combinations of k objects selected from a set of n objects is:
n!/k!(n - k)!
For the implementation of this function, don't just call factorial three times. Figure out how you would write this function by calling
the permutations function once and the factorial function once.
10.Test your combinations function. As an example, how many combinations are there when you have a set of 4 objects and choose 2? Think about it and see if you can come up with the answer on your own, then compare your answer to the result generated by your function. Also try some boundary cases, like when k > nor when one of the values is 0.
Part II: Passing by Reference
1. I want you to get some experience passing arguments by reference as well, so let's write one more function. This one will be called perms_and_combs, and it computes both the number of permutations and the number of combinations in a single function call.
2. So, declare and define a function named perms_and_combs that has a void return type. It should take the four following arguments, in this order: two ints, passed by value, which correspond to the n and k values in Part I, followed by an int passed by reference which will be
used to store the number of permutations, followed by an int passed by reference which will be used to store the number of combinations.
3. Inside the perms_and_combs function, call the permutations function and store that result in the first reference parameter.
4. Then, again inside the perms_and_combs function, call the combinations function and store that result in the second reference parameter.
5. Test the new function inside your main, as before. Remember that you can only pass variables as reference arguments to a function, so you'll need to declare two variables to hold the output of the perms_and_combs function in order to get those results back.
6. Once you feel confident that your code is working the way it should, submit it to Web-CAT. Note that when Web-CAT grades your submission, it will call the four functions that you've written directly; your mainfunction will be ignored, so focus on making sure that the functions produce the correct results and don't worry about formatting your output in any particular way. Make sure the function names, and number of parameters is the same as the description. Certain functions require you to use other functions. The TAs will check that you have followed these instructions and mark you down if haven't. You will only receive half credit for a function if it works but you haven't followed directions.