Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.
This is a Jupyter notebook. See How to use these notes.
Alice has 5 tickets to the Red Queen's ball (in addition to her own). She has 10 friends she'd like to take. She wonders how many ways she can pick 5 friends out of a total of 10.
In general she'd like to know how many ways she can pick $r$ things out of a set of $n$ things. Of course this only makes sense if $0 \le r \le n$. Let's call this function combinations so combinations(n, r) will be the number of ways to pick a subset of size r out of a set of size n.
We write a contract for the combinations function.
The contract is
def combinations( n, r ):
"""
Pre: r and n are integers such that 0 <= r and r <= n
Post: result == the number of subsets of size r of a set of size n
"""
Alice thinks about her 10 friends. Every subset will either contain her friend Bill the Lizard or it won't. First she thinks about how many sets of size 5 include Bill. There will be one such set for each way she could make a set of size 4 of out of the 9 remaining friends. That's $combinations( 9, 4 )$. What about the sets that don't include Bill. The number of those will be the number of sets of size 5 she can make out of her remaining 9 friends. That's #combinationd( 9, 5 )$ Since each set either contains Bill or doesn't, we've accounted for all sets of size 5 that can by made from her 10 friends. And we haven't counted any twice. We have
$combinations( 10, 5 ) = combinations( 9, 4 ) + combinations( 9, 5 )$
Alice's idea generalizes to most pairs of numbers, but it doesn't work when $r=0$ or when $r=n$. In general we have
$combinations( n, r ) = combinations( n-1, r-1 ) + combinations( n-1, r )$
provided $r>0$ and $r The two cases that aren't dealt with by this rule can be dealt with easily enough. Consider a set $S$ of size $n$. There is one subset of size 0, the empty set. So we have $combinations(n, 0) = 1$ for all $n \ge 0$ And there is one subset of size $n$, the set $S$ itself. So we have $combinations(n, n) = 1$ for all $n \ge 0$ So altogether we have three properties These three properties uniquely define the function, we can see this by induction on $n$. Based on the properties above we can make a table for testing. This table is the first 7 rows of an infinite table known as Pascal's triangleWe need a base case¶
Is this a definition¶
Some tests¶
n \ r
0
1
2
3
4
5
6
0
1
1
1
1
2
1
2
1
3
1
3
3
1
4
1
4
6
4
1
5
1
5
10
10
5
1
6
1
6
15
20
15
6
1
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 combinations( n, r ):
"""
Pre: n and r are integers such that 0 <= r and r <= n
Post: result == the number of subsets of size r of a set of size n
"""
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.
combinations(0, 0)
combinations(4, 0)
combinations(4, 4)
combinations(6, 2)
Now let's compare your anSwers with the first 7 rows of Pascal's triangle
pascal = [ [1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1]]
failures = set()
for n in range(0, 7) :
for r in range(0, n+1):
result = combinations(n,r)
print("c(", n, ",", r, ") =", result, end=" " )
if result != pascal[n][r]: failures.add( (n, r) )
print()
if len(failures) == 0 : print( "PASSED")
else: print( "FAILED on these inputs: ", failures )
Here is my pseudo code
function $combinations( n : nat, r : nat ) $
pre $0 \le r \le n$
post result = the number of subsets of size r of a set of size nif $r = 0$ then 1
| $r = n$ then 1
| $0 < r < n$ then $combinations( n-1, r-1) + combinations( n-1, r)$
end if
And here is the Python 3 code
def combinationsMine( n, r ):
"""
Pre: n and r are integers such that 0 <= r and r <= n
Post: result == the number of subsets of size r of a set of size n
"""
assert isinstance(n, int) and n >= 0
assert isinstance(r, int) and 0 <= r and r <= n
if r == 0: return 1
elif r == n: return 1
else: return combinationsMine(n-1, r-1) + combinationsMine(n-1, r)
combinationsMine(0, 0)
combinationsMine(4, 0)
combinationsMine(4, 4)
combinationsMine(6, 2)
Next we'll compare with Pascal's triangle.
failures = set()
for n in range(0, 7) :
for r in range(0, n+1):
result = combinationsMine(n,r)
print("c(", n, ",", r, ") =", result, end=" " )
if result != pascal[n][r]: failures.add( (n, r) )
print()
if len(failures) == 0 : print( "PASSED")
else: print( "FAILED on these inputs: ", failures )
The straightforward recursive solution that I've used is very inefficient. I'm going to ignore this problem for now. The point of these exercises is to get comfortable with creating correct recursive solutions without worrying about efficiency. Later we'll come back to the problem of making this solution efficient by using a technique called "memoization".