1

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?

cdlane
  • 40,441
  • 5
  • 32
  • 81
HelpMe
  • 91
  • 10
  • Maybe you're in the same class? https://stackoverflow.com/a/54302988/633183 – Mulan Jan 23 '19 at 17:47
  • @user633183 LOL. I didn''t think so... I am trying to improve my recursion problem-solving ability but don't know how – HelpMe Jan 23 '19 at 18:10

1 Answers1

1

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.

cdlane
  • 40,441
  • 5
  • 32
  • 81
  • Can you explain the usage of *tail? And can you give some alternative here for this * ? So, what is my problem? I didn't think carefully for all the base cases actually? Thanks. – HelpMe Jan 23 '19 at 17:11
  • @HelpMe, you tagged your question [python-3.x] so I used a Python 3 feature. The `head, *tail = array` assignment puts the first element of `array` into `head` and puts the rest of `array` into `tail`. Equivalent to `head, tail = array[0], array[1:]` I guess. – cdlane Jan 23 '19 at 17:35
  • Okay thanks. Can you just explain me what was my misconception with the recursion? I didn't think carefully for all the base cases? – HelpMe Jan 23 '19 at 18:07
  • @HelpMe, I think your concept was correct. Rather than explicitly handle the single list case, I would have preferred if I could merge all the single list items with the empty list and only have a single base case. But that didn't work out when mapping it onto a specific programming language. – cdlane Jan 23 '19 at 19:12
  • If my concept was correct I don't really understand what the problem with my recursion/code is? – HelpMe Jan 23 '19 at 19:37
  • @HelpMe, consider the input `[[1, 2, 3]]`. `len(lst)` isn't zero, but `lst[1:]` is empty. So your code returns `None`. – cdlane Jan 23 '19 at 19:46
  • Describe me your method of solving recusive/backtracking problems. You have some question of: "give me all the options that something occurs", "how many times something is appeared?". How do you to start thinking? From where to where? – HelpMe Jan 23 '19 at 20:19