Cartesian Product

'''
If list = [list1, list2, list3], where list1, list2, list3 are 3 lists, for example:
list1 = [1, 2, 3] ,   list2 = ['a', 'b'],    list3 = [4, 5] ----> return
[ [1, 'a', 4], [1, 'a', 5], [1, 'b', 4], [1, 'b', 5], .... ]
'''

def cartesianProduct(listOfLists):
    n = len(listOfLists)
    # n = the number of lists I have to combine
    if n == 1:
        return listOfLists
    elif n == 2:
        list1 = listOfLists[0]
        list2 = listOfLists[1]
        returnedList = list()
        for a in list1:
            for b in list2:
                # a = element of list1, b = element of list2
                listAB = list()
                listAB.append(a)
                listAB.append(b)
                returnedList.append(listAB)
        return returnedList
    else:
        # Now, n = 3,4,5, .... I have to combine these lists
        # I will make a recursive algorithm, where I breakm y first variable "listOfLists"
        # into 2 lists: the 1st one that has 2 lists and the remaining list
        sub1 = cartesianProduct(listOfLists[0:2])
        sub2 = listOfLists[2:]
        sub = [sub1, sub2]
        return cartesianProduct(sub)
        return -100

# MAIN FUNCTION
l1 = [5, 6]
l2 = [15, 16]
l3 = [25, 26]
l4 = [35, 36]
l12 = [l1, l2]
l123 = [l1, l2, l3]
l1234 = [l1, l2, l3, l4]
print(l12)
print(cartesianProduct(l12))
print()
print(l123)
print(cartesianProduct(l123))
print()