Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.
This is a Jupyter notebook. See How to use these notes.
Five friends go to the movie theatre. They grab five seats in a row. First the sit in alphabetical order: Alice, Bill, Cat, Dinah, Edith. Then Alice switches with Edith because she doesn't want to sit next to Bill. But Dinah wants to sit next to Edith, so Cat switches with Edith.
They wonder how many ways they can sit in the five seats. Alice says any of us could sit in the first seat. Then there are 4 of us left. So we just need to know how many ways the four people can sit in the four remaining seats. Then we can multiply that number by 5.
Alice's observation invites a generalization of the original problem. We are now interested in how many ways $n$ people can sit in $n$ seats. Here $n$ should be a positive integer. (Later we will consider the problem of putting $0$ people in $0$ seats, but for now $n$ will be 1 or 2 or 3, ... .) Let's call that number $permCount(n)$.
Aside I call it $permCount(n)$ since a permutation of a set is an ordering of all members of the set with no repetitions. The number of permutations of a set depends only on its size, not on its contents. End of Aside
We write a contract for the $permCount$ function.
Aside A contract specifies the following things
The name of the function.
The parameter list
Any constraints on the function's inputs. This is called the function'ss precondition. It is the responsibility of the coder who writes calls (the caller) to the function to ensure that the precondition is true.
The relationship between the inputs and the outputs of the function. This is called the function's postcondition. It is the responsibility of the coder who implements the function (the implementor) to ensure that the postcondition is respected by the implementation in every case in which the precondition was respect by the caller. For most of our examples the only output is the function's result, which I will call result
in postconditions
End of Aside
In the case of the permCount
function the contract is
def permCount( n ):
"""Pre: n is an integer greater than 0
Post: result == the number of permutations of a set of n things
"""
Generalizing Alice's observation, we can see that that the number of ways $n$ people can sit in $n$ seats is $n$ times $permCount(n-1)$, provided $n>1$.
Alice's observation is no help when n
is 1, since permCount(0)
isn't (yet) clearly defined. Luckly this problem is easy. There is obviously only one way that one person can sit in one seat. permcount
must obey the following two properties
The two properties above are properties that we expect permCount
to have. But they are more than that. They completely define the function, at least for arguments greater than or equal to 1
. You convince yourself of this by doing a simple inductive proof that these two properties uniquely define permCount
.
Based on the contract, here are some tests
permCount(1)
should have a result of 1
permCount(2)
should have a result of 2
permCount(3)
should have a result of 6
permCount(4)
should have a result of 24
permCount(5)
should have a result of 120
permCount( 100 )
should have a result of 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
permCount( 500 )
should have a result of 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Based on the problem analysis, we can write a design in pseudocode. In this case the pseudocode will look a lot like Python, so you can take this step if you want or skip it if you don't.
[Put your pseudocode here]
Before coding, you should check that your design will work. Here is a checklist
Complete the following function
def permCount( n ) :
"""Pre: n is an integer greater than 0
Post: result == the number of permutations of a set of n things
"""
# Put your code here
If you wrote pseudocode, check that your design is consistant with the pseudocode. If you didn't write pseudocode, use the checklist above to check your code.
Below are some tests. After you define the function, you can run these tests and compare the answers with expected answers above.
permCount(1) # Expect 1
permCount(2) # Expect 2
permCount(3) # Expect 6
permCount(4) # Expect 24
permCount(5) # Expect 120
permCount(100) # Expect 933262154...00000000
permCount(500) # Expect 1220136...00000000000000
def permCountMine( n ) :
"""Pre: n is an integer greater than 0
Post: result == the number of permutations of a set of n things
"""
assert isinstance(n, int) and n > 0
if n==1 :
return 1
else:
return n * permCountMine( n-1 )
permCountMine(1)
permCountMine(2)
permCountMine(3)
permCountMine(4)
permCountMine(5)
permCountMine(100)
permCountMine(500)
As you likely know, the permCount
function is normally called the factorial
function and it has lots of uses.
We can extend the function to 0 as follows. How many permutations are there of a set of size 0? The only set of size 0 is the empty set $\emptyset$ and there is only one sequence we can make that contains only elements of this set. That is the empty sequence. Also the empty sequence contains every element of the set and there are no repetitions. So the set of all permutations of $\emptyset$ is $\{ [\,] \}$; this set has size 1, so the factorial of 0 should be 1. Note that Alice's law now holds for n
equal to 1.
The new contract and code is
def factorial( n ) :
"""Pre: n is an integer greater than or equal to 0
Post: result == the factorial of n
"""
assert isinstance(n, int) and n >= 0
if n == 0 :
return 1
else:
return n * factorial( n-1 )
factorial(0)
factorial(1)
factorial(2)
factorial(3)
factorial(4)
factorial(5)
factorial(100)
factorial(500)
Another approach to factorial is to use an accumulator. An accumulator is an extra parameter that we use to record a partial result. We use two functions: factorialWithAccumulator
and factorialWithAccumulatorHelper
. The helper function has the accumulator.
def factorialWithAccumulator( n ) :
"""Pre: n is an integer greater than or equal to 0
Post: result == the factorial of n
"""
assert isinstance(n, int) and n >= 0
return factorialWithAccumulatorHelper( n, 1 )
def factorialWithAccumulatorHelper( n, accumulator ) :
"""Pre: n is an integer greater than or equal to 0 and accumulator is an integer.
Post: result == the product of accumulator * the factorial of n
"""
if n == 0 :
# accumulator * 0! = accumulator * 1 = accumulator
return accumulator
else :
# accumulator * n! = accumulator * n * (n-1)! = (n*accumulator) * (n-1)!
return factorialWithAccumulatorHelper( n-1, n*accumulator )
factorialWithAccumulator( 0 )
factorialWithAccumulator( 5 )
factorialWithAccumulator( 500 )
We can apply tail recursion optimization and inlining to the last pair of functions to get an slightly more efficient implementation. I won't explain these concepts here in detail. But carefully compare this version with the previous. There will be more examples later.
def iterativeFactorial( n ) :
"""Pre: n is an integer greater than or equal to 0
Post: result == the factorial of n
"""
assert isinstance(n, int) and n >= 0
accumulator = 1
while n > 0 :
accumulator = n*accumulator
n = n-1
return accumulator
iterativeFactorial(0)
iterativeFactorial(5)
iterativeFactorial(500)
One advantage of the nonrecursive version is that it have handle larger inputs. Try any of the recusive versions with an input of 5000 and I suspect that you won't get an answer becuase Python implementations limit the depth of recursion allowed. However our iterative factorial should have no problem with large inputs.
iterativeFactorial(5000)
By the way there are just over 1000 zeros at the end of that factorial. In fact there are 1249 zeros. How did I know that without counting them?