I am practicing solving recursion and backtracking exercises. I'm given a problem to print all the cartesian products of a list of lists, where every sub-list contains only different chars. Of course, if any one of the sub-lists is empty - the final product is an empty list.
I immediately thought of solving it recursively\backtrackingly. I'm bad at recursion -- the recommendation people gave me is: Look at recursion as a black-box, only think of some appropriate base-case, and assume inductively you are given the answer for n-1, and make the step of the recursion.
So here is what I thought, "What is the base case?" When the list of lists is empty - I'll print an empty list. If not, I return the first char of the first sub-list, plus, the recursive call to the list of lists from the next sub-list.
def cartesian_product(lst):
if len(lst)==0:
return []
for c in cartesian_product(lst[1:]):
for s in c:
return [lst[0][0]] + [s]
I guess the problem here is because I don't save the current sub-list, I'm always at the first sub-list. But, there is an error of 'NoneType' and I don't know why.
How do I know when I need a function helper? When can I solve it how I described that people told me?
First, although this is recursion, I don't consider it backtracking as we're not going to assemble and then potentially reject, a candidate solution. We conceptually think of the empty list as our base case but Python's looping logic won't run with an empty list. So instead we work with two base cases, an empty argument list and an argument list of just a single sublist.
If our argument only has a single sublist, [1, 2, 3], then the result is [[1], [2], [3]] otherwise the solution is to attach every member of the initial sublist to the front (of a copy) of the result of calling ourselves recursively on the rest of the sublists:
def cartesian_product(array):
product = []
if array: # avoid empty base case
head, *tail = array
if tail: # not a base case
for t in cartesian_product(tail):
for h in head:
product.append([h] + t)
else: # one list base case
product = [[h] for h in head]
return product
This logic also gives us the desired behavior that an empty list appearing as any of the argument sublists causes an empty list to be returned as a result.