Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.

This is a Jupyter notebook. See How to use these notes.

# Combinations¶

## The problem¶

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.

### A generalization¶

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.

### A contract¶

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
"""


## Problem analysis¶

### Alice's observation¶

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

### We need a base case¶

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

1. $combinations(n, 0) = 1$ for all $n \ge 0$.
2. $combinations(n, n) = 1$ for all $n \ge 0$.
3. $combinations(n, r) = combinations( n-1, r-1 ) + combinations( n-1, r )$ for all $0 < r < n$.

### Is this a definition¶

These three properties uniquely define the function, we can see this by induction on $n$.

### Some tests¶

Based on the properties above we can make a table for testing.

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

This table is the first 7 rows of an infinite table known as Pascal's triangle

## Design¶

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.

## Analyze design¶

Before coding, you should check that your design will work. Here is a checklist

• Is every case allowed by the precondition covered?
• Does the code do the right thing (i.e. return a result allowed by the postcondition) in each case?
• Is every recursive call smaller in some sense than its parent call?

## Code¶

Complete the following function

In [54]:
    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
"""


## Analyze code¶

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.

## Test¶

Below are some tests. After you define the function, you can run these tests and compare the answers with expected answers above.

In [55]:
combinations(0, 0)

In [56]:
combinations(4, 0)

In [57]:
combinations(4, 4)

In [58]:
combinations(6, 2)


Now let's compare your anSwers with the first 7 rows of Pascal's triangle

In [59]:
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 )

c( 0 , 0 ) = None
c( 1 , 0 ) = None c( 1 , 1 ) = None
c( 2 , 0 ) = None c( 2 , 1 ) = None c( 2 , 2 ) = None
c( 3 , 0 ) = None c( 3 , 1 ) = None c( 3 , 2 ) = None c( 3 , 3 ) = None
c( 4 , 0 ) = None c( 4 , 1 ) = None c( 4 , 2 ) = None c( 4 , 3 ) = None c( 4 , 4 ) = None
c( 5 , 0 ) = None c( 5 , 1 ) = None c( 5 , 2 ) = None c( 5 , 3 ) = None c( 5 , 4 ) = None c( 5 , 5 ) = None
c( 6 , 0 ) = None c( 6 , 1 ) = None c( 6 , 2 ) = None c( 6 , 3 ) = None c( 6 , 4 ) = None c( 6 , 5 ) = None c( 6 , 6 ) = None
FAILED on these inputs:  {(6, 6), (3, 0), (2, 1), (6, 2), (5, 1), (4, 0), (3, 3), (5, 5), (4, 4), (6, 3), (5, 0), (2, 2), (4, 1), (1, 1), (6, 4), (3, 2), (0, 0), (5, 4), (6, 0), (4, 2), (1, 0), (6, 5), (5, 3), (6, 1), (3, 1), (2, 0), (4, 3), (5, 2)}


# My Solution¶

## Design¶

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 n

if $r = 0$ then 1
| $r = n$ then 1
| $0 < r < n$ then $combinations( n-1, r-1) + combinations( n-1, r)$
end if

## Code¶

And here is the Python 3 code

In [60]:
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)


## Test¶

In [53]:
combinationsMine(0, 0)

Out[53]:
1
In [44]:
combinationsMine(4, 0)

Out[44]:
1
In [45]:
combinationsMine(4, 4)

Out[45]:
1
In [46]:
combinationsMine(6, 2)

Out[46]:
15

Next we'll compare with Pascal's triangle.

In [50]:
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 )

c( 0 , 0 ) = 1
c( 1 , 0 ) = 1 c( 1 , 1 ) = 1
c( 2 , 0 ) = 1 c( 2 , 1 ) = 2 c( 2 , 2 ) = 1
c( 3 , 0 ) = 1 c( 3 , 1 ) = 3 c( 3 , 2 ) = 3 c( 3 , 3 ) = 1
c( 4 , 0 ) = 1 c( 4 , 1 ) = 4 c( 4 , 2 ) = 6 c( 4 , 3 ) = 4 c( 4 , 4 ) = 1
c( 5 , 0 ) = 1 c( 5 , 1 ) = 5 c( 5 , 2 ) = 10 c( 5 , 3 ) = 10 c( 5 , 4 ) = 5 c( 5 , 5 ) = 1
c( 6 , 0 ) = 1 c( 6 , 1 ) = 6 c( 6 , 2 ) = 15 c( 6 , 3 ) = 20 c( 6 , 4 ) = 15 c( 6 , 5 ) = 6 c( 6 , 6 ) = 1
PASSED


# Going further¶

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".