We continued discussing recursion. We also discussed memoization and demonstrated it. Then we reviewed some properties of prime numbers and used them for primality testing.
and finally changing your recursive implementation so that it will search for the key in the dictionary before making the recursive calls, and save the key:value pair after obtaining the value for a certain input.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Question 2(a) from the 2015 fall semester exam (Moed B).
Given a list $L$ of non-negative integers with $len(L) = d$ we consider $L$ as a point in a $d$-dimensional space.
For example: $L = [0, 0, 0]$ represents the origin in a $3$-dimensional space.
Our goal is to find how many ways we have of getting from $[0, \ldots, 0]$ to $L$ by advancing only forward.
For example, if $L=[1, 2]$ then we have three such paths:
Again, we first think of the base case, and then reduce big problems to smaller ones.
This gives rise to a simple recursive algorithm:
def cnt_paths(L):
if all_zeros(L):
return 1
result = 0
for i in range(len(L)):
if L[i] != 0:
L[i] -= 1
result += cnt_paths(L)
L[i] += 1
return result
def all_zeros(L):
for i in L:
if i != 0:
return False
return True
print(cnt_paths([3,4,5]))
27720
Let's take a simple case where $L = [n, n, \ldots, n]$ and $|L| = d$. I.e. - we are in a $d$-dimensional space and we want to get to $[n, \ldots, n]$.
How does the recursion tree for this problem looks like? At each node we have $k$ recursive calls where $k$ is the number of non-zero coordinates in the current list. This means that at the $i$th level of the recursion we have $sum(L) = nd - i$, and so each path in the tree has length exactly $nd$ and in particular the depth of the tree is $nd$.
Additionally, the leaves in the tree are exactly the "legal paths" which we count.
If $cnt$ is the result of the function (i.e., the number of such legal paths, i.e., the number of leaves) the above means that the recursion tree has size at most $nd \cdot cnt$ (the level of the leaves is the "widest" level).
Since each node does $O(1)$ work, this is also a bound for the running time of the function.
Can we do better?
Can you think of a combinatorial solution for cnt_paths? Let's take the case above where $L = [n, n, \ldots, n]$ and $|L| = d$.
In each step we subtract $1$ from one of the $d$ coordinates (which is currently positive) and in exactly $nd$ steps we need to get to the all-zero vector.
Think about the first coordinate - there are precisely $n$ steps along our path where we change this coordinate, thus we have $\binom{nd}{n}$ options to choose where the moves for the first coordinate are located.
What about the second coordainte? Well now we are left with $nd - n = n(d-1)$ places out of which we again pick $n$ places to advance the second coordinate. By indcution, we get: $$cnt = \prod_{i=1}^d \tbinom{n(d-i+1)}{n} = \prod_{i=1}^d \tbinom{ni}{n} $$
How long does it take to compute this number? We need to multiply $d$ elements, and for each of those we need to compute factorials and divide numbers in the range of $1,\ldots,n$. This is clearly done in time polynomial in $d,n$.
And how big is $cnt$ exactly? Recall that $cnt$ is a bound on the running time of cnt_paths.
We now claim that $cnt = exp(n,d)$. To see this, we write it explicitly:
$$cnt = \tbinom{n}{n}\cdot \tbinom{2n}{n} \cdots \tbinom{dn}{n} = \frac{n!}{(n-n)! n!} \cdot \frac{(2n)!}{(2n-n)! n!} \cdot \frac{(3n)!}{(3n-n)! n!}\cdots \frac{(nd)!}{(nd-n)! n!} $$This product has a telescopic property - thus we can cancel out elements and get:
$$cnt = \frac{(nd)!}{(n!)^d} = \frac{1\cdot 2 \cdot 3 \cdots \cdot nd}{(1 \cdot 2 \cdots n) \cdots(1 \cdot 2 \cdots n)} $$Break this product into two terms:
$$cnt = \frac{1 \cdots 2n}{n! \cdot n!} \cdot \frac{(2n + 1) \cdots nd }{(n!)^{d - 2}}$$The first multiplicand is clearly larger than $1$, as for the second, each term in the numerator is at least $2n$ and each term in the denominator is at most $n$ thus clearly: $$cnt \gg \frac{2n \cdot 2n \cdots 2n}{n \cdot n \cdot n} = 2^{dn - 2n} = exp(n,d)$$
Conclusion? Using the combinatorial computation we reduce a running time which is exponential in $n,d$ into a running time polynomial in $n,d$.
The number of sets of size $k$ selected from a set of $n$ elements (with no repetitions) Recursive formula (Pascal): $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ where the stopping criterion is $\binom{n}{0} = \binom{n}{n} = 1$
The time complexity of binom is exponential in $n$ (worst case behaviour is when $k=\frac{n}{2}$)
def binom(n,k):
if n < 0 or k < 0 or n < k:
return 0
elif (k==0 or n==k):
return 1
return binom(n-1,k-1) + binom(n-1,k)
binom(4,2)
6
def binom_trace(n,k):
result = binom_trace(n,k)
return result
def binom_trace(n,k,indent=1):
#indent = how much to indent the printouts
if (k<0 or n<0 or n<k): # safety checks
return 0
elif (k==0 or k==n): # halting conditions
print(">>"*indent + "({},{})".format(n,k))
print("<<"*indent + "({},{})".format(n,k))
return 1
print(">>"*indent + "({},{})".format(n,k))
indent+=1
val = binom_trace(n-1,k,indent) + binom_trace(n-1,k-1,indent)
indent-=1
print("<<"*indent + "({},{})".format(n,k))
return val
binom_trace(4,2)
>>(4,2) >>>>(3,2) >>>>>>(2,2) <<<<<<(2,2) >>>>>>(2,1) >>>>>>>>(1,1) <<<<<<<<(1,1) >>>>>>>>(1,0) <<<<<<<<(1,0) <<<<<<(2,1) <<<<(3,2) >>>>(3,1) >>>>>>(2,1) >>>>>>>>(1,1) <<<<<<<<(1,1) >>>>>>>>(1,0) <<<<<<<<(1,0) <<<<<<(2,1) >>>>>>(2,0) <<<<<<(2,0) <<<<(3,1) <<(4,2)
6
Now with memoization:
def binom_fast(n,k):
d = {}
return binom_mem(n,k,d)
def binom_mem(n,k,mem):
if n < 0 or k < 0 or n < k:
return 0
elif (k==0 or n==k):
return 1
if (n,k) not in mem:
mem[(n,k)] = binom_mem(n-1,k, mem) + \
binom_mem(n-1,k-1, mem)
return mem[(n,k)]
binom_fast(4,2)
binom_fast(50,25)
126410606437752
Printing the recursive calls, with memoization:
def binom_fast_trace(n,k):
mem = dict()
result = binom_mem_trace(n,k,mem)
return result
def binom_mem_trace(n,k,mem,indent=1):
#indent = how much to indent the printouts
if (k<0 or n<0 or n<k): # safety checks
return 0
elif (k==0 or k==n): # halting conditions
print(">>"*indent + "({},{})".format(n,k))
print("<<"*indent + "({},{})".format(n,k))
return 1
print(">>"*indent + "({},{})".format(n,k))
indent+=1
if (n,k) not in mem:
mem[(n,k)] = binom_mem_trace(n-1,k,mem,indent) + binom_mem_trace(n-1,k-1,mem,indent)
indent-=1
print("<<"*indent + "({},{})".format(n,k))
return mem[(n,k)]
binom_fast_trace(4,2)
>>(4,2) >>>>(3,2) >>>>>>(2,2) <<<<<<(2,2) >>>>>>(2,1) >>>>>>>>(1,1) <<<<<<<<(1,1) >>>>>>>>(1,0) <<<<<<<<(1,0) <<<<<<(2,1) <<<<(3,2) >>>>(3,1) >>>>>>(2,1) <<<<<<(2,1) >>>>>>(2,0) <<<<<<(2,0) <<<<(3,1) <<(4,2)
6
Time complexity = number of different visited cells * number of visits per cell * time per visit (not including recursive calls)
A bus driver needs to give an exact change and she has coins of limited types. She has infinite coins of each type. Given the amount of change ($amount$) and the coin types (the list $coins$), how many ways are there?
def change(amount, coins):
if amount == 0:
return 1
elif amount < 0 or coins == []:
return 0
return change(amount, coins[:-1]) +\
change(amount - coins[-1], coins)
change(5, [1,2,3])
5
Now with memoization:
def change_fast(amount, coins):
d = {}
return change_mem(amount, coins, d)
def change_mem(amount, coins, d):
if amount == 0:
return 1
elif amount < 0 or coins == []:
return 0
#if (amount, tuple(coins)) not in d:
if (amount, len(coins)) not in d:
#d[(amount, tuple(coins))] = \
d[(amount, len(coins))] = \
change_mem(amount, coins[:-1], d) +\
change_mem(amount - coins[-1], coins, d)
#return d[(amount, tuple(coins))]
return d[(amount, len(coins))]
change_fast(500, [1,3,2])
21084
The $N$ queens problem is to determine how many possibilities are there to legally place $N$ queens on an $N$-by-$N$ chess board. Legally means no queen threatens another queen.
Solution: We build the solution incrementally, column by column. We maintain a partial solution (implemented as a list), which is initially empty.
The function $legal(partial, i)$ is given:
It returns True if it is legal to place a queen in the next column on row $i$, given the partial placement $partial$
def legal(partial, i):
''' Can we place a queen in the next column in row i ? '''
# any queens in the same row to the left ?
left = [j for j in partial if j==i]
# diagonal up - left
diag_up = [j for j in partial if j - partial.index(j) == i - len(partial)]
# diagonal down - left
diag_down = [j for j in partial if j + partial.index(j) == i + len(partial)]
res = ( left == diag_up == diag_down == [])
return res
The solution:
def queens (n, show = True):
''' how many ways to place n queens on an nXn board ? '''
partial = [] # list representing partial placement of queens
return queens_rec (n, partial, show)
def queens_rec (n, partial, show):
''' Given a list representing partial placement of queens ,
can we legally extend it ? '''
if len(partial) == n: # all n queens are placed legally
return 1
else:
cnt = 0
for i in range(n):
# try to place a queen in row i of the next column
if legal(partial, i):
cnt += queens_rec(n, partial + [i], show)
return cnt
Some intuition: assume we can find a solution for placing $k<N$ queens, how do we expand the solution to $k+1$? queens_rec returns the number of possible legal placements for $N$ queens, where $k$ are already placed at the leftmost columns and there are $N-k$ queens left to place. The recursive idea: Legally place queen number $(k+1)$ and recursively solve the problem, when there is one less queen to place.
Note that the complexity is $O(N!)$ (greater than $O(2^N)$)
Question from a past exam.
Some examples:
choose_sets([1,2,3,4], 0) ---> [[]] choose_sets([1,2,3], 1) ---> [[2, 1], [3, 1], [4, 1], [3, 2], [4, 2], [4, 3]] but these output examples are valid as well: choose_sets([1,2,3,4], 4) ---> [[]]
def choose_sets(lst,k):
if k==0:
return [[]]
elif len(lst)<k:
return []
tmp = choose_sets(lst[1:],k-1)
for e in tmp:
e.append(lst[0])
tmp.extend(choose_sets(lst[1:],k))
return tmp
#choose_sets([1,2,3,4], 0)
choose_sets([1,2,3], 2)
#choose_sets([1,2,3,4], 4)
[[2, 1], [3, 1], [3, 2]]