Find out all possible cartesian products using Recursion

November 3, 2022

The function takes in a string (str) s and an integer (int) n .

The function returns a list (list) of all Cartesian product of s with length n
The expression product(s,n) can be computed by adding each character in s to the
result of product(s,n-1) .

    >>> product('ab',3)
    'aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']

My attempt:

def product(s, n):

  if n == 0:
    return ""

  string = ''
  for i in range(len(s)):
    string += s[i] + product(s, n - 1)
  return string

Disclaimer: It doesn’t work^

>Solution :

Your code is building a single string. That doesn’t match what the function is supposed to do, which is return a list of strings. You need to add the list-building logic, and deal with the fact that your recursive calls are going to produce lists as well.

I’d do something like this:

def product(s, n):
  if n == 0:
    return ['']

  result = []
  for prefix in s:                    # pick a first character
    for suffix in product(s, n-1):    # recurse to get the rest
      result.append(prefix + suffix)  # combine and add to our results
  return result

This produces the output in the desired order, but it recurses a lot more often than necessary. You could swap the order of the loops, though to avoid getting the results in a different order, you’d need to change the logic so that you pick the last character from s directly while letting the recursion produce the prefix.

def product(s, n):
  if n == 0:
    return ['']

  result = []
  for prefix in product(s, n-1):      # recurse to get the start of each string
    for suffix in s:                  # pick a final character
      result.append(prefix + suffix)  # combine and add to our results
  return result