Calculate the Cartesian product with functional programming

Question

I’m writing a Python function that takes two lists and returns a list of tuples with the Cartesian product of the input function. I cannot use any ready-made Python library function.

Ex:

print(cartesiano([1,2],[11,22]))
# [(1, 11), (1,22), (2,11), (2, 22)]

My program is printing this: [(1, 11), (2, 22)]. I’m not managing to fix the recursion.

def cartesiano(lista1,lista2):

def aux(l1,l2):
    if l1==[] and l2==[]:
       return []

    return [(l1[0],l2[0])] +aux(l1[1:],l2[1:])       

return aux(lista1, lista2) 

I can’t use repeat loops, as it’s much more intuitive. It’s a matter of functional programming, no loops, etc...

Answer 1

In an approach that reminds me a little more the functional and the logic, we can think of list heads and list body. The old function CAR and CDR of Lisp see me head.

The basic function of the Cartesian product is described more or less like this using CAR and CDR (on lists of numbers):

produto_cartesiano(list1, list2):
  se list1 é lista vazia ou list2 é lista vazia:
    retorne {}
  senão se list1 não é lista:
    retorne { (list1, CAR(list2)) U produto_cartesiano(list1, CDR(list2)) }
  senão:
    retorne { produto_cartesiano(CAR(list1), list2) U produto_cartesiano(CDR(list1), list2) }

In Python? No ties? I still can’t think of a direct way. But we can take a somewhat more direct approach Prolog. I know that the logical paradigm is not exactly what is desired, but it gives a disguised one. It helps to avoid the ties. Here, the question is to pass as argument the return list. In the logical paradigm you wouldn’t build the list, you would infer the list, it’s a very different question. Here, we will actually insert the results in the return list. So, we can make the Cartesian product like this:

def produto_cartesiano(lista1, lista2, resultado = []):
  if lista1 == [] or lista2 == []:
    return resultado
  elif !isinstance(lista1, list):
    resultado.append((lista1, lista2[0]))
    return produto_cartesiano(lista1, lista2[1:], resultado)
  else:
    produto_cartesiano(lista1[0], lista2, resultado)
    return produto_cartesiano(lista1[1:], lista2, resultado)

Note that I am using CAR and CDR in a more idiomatic way in Python, with lista[0] and lista[1:].

Just to remind you here, this answer applies to lists of numbers. Does not apply to generalized sets, including sets that may have other sets as their elements.

---

In your reply, you walked at the same time on the two lists in the recursive call, more or less like this:

cartesiano(l1, l2):
  se l1  é lista vazia e l2 é lista vazia
    return {}
  return { (CAR(l1), CAR(l2)) U cartesiano(CDR(l1), CDR(l2)) }

This eliminates many elements of the result. Be L1 X L2 the Cartesian product, you are eliminating the subsets CDR(L1) X CAR(L2) and CAR(L1) X CDR(L2), and also some other subsets due to recursion. Its halting condition is also strange because the definition of Cartesian product says that if one of the sets is the empty set, the result will also be empty. This means that it should be a OR, not a AND.

Roughly, a Cartesian product would be composed of the following subsets:

L1 X L2 =
    ({CAR(L1)} X {CAR(L2)}) U
    ({CAR(L1)} X CDR(L2)) U
    (CDR(L1) X {CAR(L2)}) U
    (CDR(L1) X CDR(L2))

Stand out, ({CAR(L1)} X {CAR(L2)}) U ({CAR(L1)} X CDR(L2)) = {CAR(L1)} X L2; and similarly to (CDR(L1) X {CAR(L2)}) U (CDR(L1) X CDR(L2)) = CDR(L1) X L2

So we have to:

L1 X L2 =
    ({CAR(L1)} X {CAR(L2)}) U
    ({CAR(L1)} X CDR(L2)) U
    (CDR(L1) X {CAR(L2)}) U
    (CDR(L1) X CDR(L2)) =
    ({CAR(L1)} X L2) U
    (CDR(L1) X L2)

Notice the resemblance to my recursion?

---

Now, what about for generalized sets? Generalized sets contain sets within sets.

Getting the full formula:

L1 X L2 =
    ({CAR(L1)} X {CAR(L2)}) U
    ({CAR(L1)} X CDR(L2)) U
    (CDR(L1) X {CAR(L2)}) U
    (CDR(L1) X CDR(L2))

The known case of recursion is with empty sets. But, I can also state that, like CAR(L) returns an element belonging to L, we have to {CAR(L1)} X {CAR(L2)} is equal to the unit set {[CAR(L1), CAR(L2)]} whose element is the tuple formed by the first elements of L1 and L2.

Thus, the recursive formula for both nonempty sets:

L1 X L2 =
    {[CAR(L1), CAR(L2)]} U
    ({CAR(L1)} X CDR(L2)) U
    (CDR(L1) X {CAR(L2)}) U
    (CDR(L1) X CDR(L2))

Therefore, the recursive function would be:

def produto_cartesiano(l1, l2, resultado = []):
  if l1 == [] or l2 == []:
    return resultado
  else:
    car1 = l1[0]
    cdr1 = l1[1:]

    car2 = l2[0]
    cdr2 = l2[1:]

    resultado.append( (car1, car2) )
    produto_cartesiano([ car1 ], cdr2, resultado)
    produto_cartesiano(cdr1, [ car2 ], resultado)
    return produto_cartesiano(cdr1, cdr2, resultado)