A friend of mine was complaining at work the other day about a programming assignment he had, frustrated that he couldn’t think of the answer. I asked him if he’d email me the basic premise of the assignment so I could tackle it myself after finals were over, and he agreed. Here’s what he sent me:
Write a program that returns the number of permutations of the set {A, B, C, D, E, F} where A appears before D.
The reason most people in that class had a problem with this assignment is because they hadn’t yet had Probability and Statistics. What you have to throw away is the concept of the letters “A” and “D” and where they appear in the list. You only need to concern yourself with the blanks they occupy and how many ways these blanks can be arranged. A Permutation is an arrangement of items in a set where order matters, and where there’s no replacement of items. This value is generalized by n! where n is the size of the set.
At first glance, this task seems daunting, since we’re not dealing with numbers. Sure, I can factorial an integer, but how do you factorial D? As I alluded before, you don’t have to. The easiest way to think about this — and make no mistake, this is primarily a cognitive assignment — is to imagine all the permutations of the set where “A” is first. Since “D” will always fall after “A” in this case, all we have to calculate now is how many permutations of the subset from “B” to “F” there are. That is as simple as calculating 5! using the factorial() method we’ve come to know and love.
That’s our first number, now we need to find our second one, where “A” is second in the list. This will be the same factorial(5) call as before, but we have to subtract from this total the number of times “D” appears before “A”. That set looks like “{D, A, X, X, X, X}” where the X’s are the other letters. And again, notice it doesn’t matter what those letters are, just that there are four blanks we’re swapping around. So “A” appears in the second slot 5! times, and “D” appears before “A” a subset of those times, which is the number of ways the remaining four letters can be arranged. The final calculation for the second number is factorial(5) - factorial(4).
And this pattern repeats itself for each successive number, up to the calculation where “A” appears sixth in the set. That calculation looks like this:
factorial(5) - factorial(4) - factorial(4) - factorial(4) - factorial(4) - factorial(4)
That is one factorial(5) for our “A” position, and one factorial(4) for each possible position of “D”. Since there are five blanks before “A” this time, that’s five factorial(4) calculations. If you are very familiar with factorials, you will notice that 5 × 4! = 5!. So what we really have here is 5! – 5!, which is obviously 0. And that makes sense, because when “A” is last in the list, there are no permutations where “A” appears before “D”.
Once you see the pattern, the program practically writes itself. Now add up the six numbers, and you have your total. You want to know what’s really interesting? It’s the same number, no matter which two letters you pick. Remember: what’s in the blanks doesn’t matter. I hope I didn’t math you out too much this time.
~Jonathan
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | /********************************* Programmer: Jonathan Landrum Program: permutations.cpp Date: 1 May 2012 --------------------------------- Assumptions: None. Dependencies: None. *********************************/ #include <iostream> using namespace std; long int factorial (long int in); // -------------------------------------------------- // main(): // // Calls the factorial function, and returns results. // -------------------------------------------------- int main() { int first, second, third, fourth, fifth, sixth; cout << "/====================================\\" << endl; cout << "| |" << endl; cout << "| C++ Permutations |" << endl; cout << "| |" << endl; cout << "\\====================================/" << endl; cout << endl; cout << "This program returns the number of" << endl; cout << "permutations there are of the letters" << endl; cout << "from A to F where A appears before D." << endl; cout << endl; cout << "--------------------------------------" << endl; cout << "Processing..." << endl; cout << endl; /**************************** Each factorial(5) is where A appears in the set, and each factorial(4) is an exception where D appears before A. Notice that when A is first, it doesn't matter where D appears. We could have more easily multiplied our factorial calculations and gained some speed, but I wanted to show WHY these numbers are right. ****************************/ first = factorial(5); // {D,A,X,X,X,X} second = factorial(5) - factorial(4); // {D,X,A,X,X,X} & {X,D,A,X,X,X} third = factorial(5) - factorial(4) - factorial(4); // {D,X,X,A,X,X} & {X,D,X,A,X,X} & {X,X,D,A,X,X} fourth = factorial(5) - factorial(4) - factorial(4) - factorial(4); // {D,X,X,X,A,X} & {X,D,X,X,A,X} & {X,X,D,X,A,X} & {X,X,X,D,A,X} fifth = factorial(5) - factorial(4) - factorial(4) - factorial(4) - factorial(4); /**************************** Notice that factorial(4) x 5 is equal to factorial(5). So this is a wasted calculation for the sake of example. ****************************/ // {D,X,X,X,X,A} & {X,D,X,X,X,A} & {X,X,D,X,X,A} & {X,X,X,D,X,A} & {X,X,X,X,D,A} sixth = factorial(5) - factorial(4) - factorial(4) - factorial(4) - factorial(4) - factorial(4); cout << " " << first << " <- All where A is 1st" << endl; cout << " " << second << " <- All where A is 2nd" << endl; cout << " " << third << " <- All where A is 3rd" << endl; cout << " " << fourth << " <- All where A is 4th" << endl; cout << " " << fifth << " <- All where A is 5th" << endl; cout << "+ " << sixth << " <- All where A is 6th" << endl; cout << "----" << endl; cout << " " << first + second + third + fourth + fifth + sixth << endl; cout << endl; cout << "Process complete." << endl; cout << "--------------------------------------" << endl; cout << "\\\\//_ Live long and prosper." << endl; } // -------------------------------------------------- // factorial(): // // Recursive function. // Returns long int, accepts (long int in). // // Calculates the factorial of the given number. // -------------------------------------------------- long int factorial (long int in) { long int result = 0; if (in == 0) result = 1; else result = in * factorial(in - 1); return result; } // End factorial |



