Cartesian product of two tuples - python

Question

I'm solving exercise 4 from Discussion 3 of Berkley's CS 61A (2012) (see page 4):

Fill in the definition of cartesian_product. cartesian_product takes in two tuples and returns a tuple that is the Cartesian product of those tuples. To find the Cartesian product of tuple X and tuple Y, you take the first element in X and pair it up with all the elements in Y. Then, you take the second element in X and pair it up with all the elements in Y, and so on.

def cartesian_product(tup_1, tup_2):
    """Returns a tuple that is the cartesian product of tup_1 and tup_2.
    >>> X = (1, 2)
    >>> Y = (4, 5)
    >>> cartesian_product(X, Y)
    ((1, 4), (4, 1) (1, 5), (5, 1), (2, 4), (4, 2) (2, 5), (5, 2))
    """

My solution:

def cartesian_product_recursive(tup_1, tup_2):
    """Returns a tuple that is the cartesian product of tup_1 and tup_2
    
    >>> X = (1, 2)
    >>> Y = (4, 5)
    >>> cartesian_product(X, Y)
    ((1, 4), (4, 1), (1, 5), (5, 1), (2, 4), (4, 2), (2, 5), (5, 2))
    """
    length1 = len(tup_1)
    length2 = len(tup_2)
    def product(tup_1, tup_2, index1, index2):
        if index1 == length1:
            return ()
        elif index2 == length2:
            return product(tup_1, tup_2, index1 + 1, 0)
        else:
            return ((tup_1[index1], tup_2[index2]),) + ((tup_2[index2], tup_1[index1]), ) + product(tup_1, tup_2, index1, index2 + 1)
    return product(tup_1, tup_2, 0, 0)

I know that Python has a built-in function itertools.product, but at this point in the course, the only operations on tuples that we have studied are indexing [1] [-1], slicing [1:], and concatenation +, so my solution needs to restrict itself accordingly.

Can this solution be improved?

Answer 1

If you can use the built-in itertools module, then itertools.product is probably the easiest, but it probably not allowed. itertools.product creates an iterable of the cartesion product of two sequences. Since you want it with both the tup1 element first and the tup2 element first, you need to do it twice:

def cartesian_product_itertools(tup1, tup2):
    return tuple(product(tup1, tup2))+tuple(product(tup2, tup1))

The second approach would be to roll your own generator-based solution, using the yield statement. This can then be converted to a tuple in the same way. You need an inner function to handle the generator, and an outer function to convert it to a tuple:

def cartesian_product_iter(tup1, tup2):
    def cartesian_product_iter_inner(tup1, tup2):
        for t1 in tup1:
            for t2 in tup2:
                yield t1, t2
                yield t2, t1
    return tuple(cartesian_product_iter(tup1, tup2))

You can also do a similar looping version:

def cartesian_product_loop(tup1, tup2):
    res = ()
    for t1 in tup1:
        for t2 in tup2:
            res += ((t1, t2), (t2, t1))
    return res

For a recursive version, you can greatly simplify by using slices instead of indexes:

def cartesian_product_recursive(tup_1, tup_2):
    res = ((tup_1[0], tup_2[0]), (tup_2[0], tup_1[0]))
    if len(tup_2) == 1:
        return res
    res += cartesian_product_recursive(tup_1[:1], tup_2[1:])
    if len(tup_1) == 1:
        return res
    res += cartesian_product_recursive(tup_1[1:], tup_2)
    return res

I prefer short-circuiting, hence the returns. If you prefer if...else, here is an equivalent implementation:

def cartesian_product_recursive_2(tup_1, tup_2):
    res = ((tup_1[0], tup_2[0]), (tup_2[0], tup_1[0]))
    if len(tup_2) > 1:
        res += cartesian_product_recursive_2(tup_1[:1], tup_2[1:])
    if len(tup_1) > 1:
        res += cartesian_product_recursive_2(tup_1[1:], tup_2)
    return res

Answer 2

It's long after the question was asked, but for future reference, here's a concise and "Pythonic" solution to the Cartesian product problem:

def cartesian_product(tup1, tup2):
    """Returns a tuple that is the Cartesian product of tup_1 and tup_2

    >>> X = (1, 2)
    >>> Y = (4, 5)
    >>> cartesian_product(X, Y)
    ((1, 4), (1, 5), (2, 4), (2, 5))
    """
    return tuple((t1, t2) for t1 in tup1 for t2 in tup2)

Note that, as @Gareth Rees points out, this actually produces the Cartesian product as defined in set theory. In the strict mathematical definition, the resulting set A x B is made up of ordered pairs from A and B. The set from the problem statement would be (A x B) U (B x A).

However, if the problem were restated to beg for this latter set, not calling it (incorrectly) the Cartesian product, then this implementation would suffice:

def cartesian_product_and_inverse(tup1, tup2):
    prod = tuple((t1, t2) for t1 in tup1 for t2 in tup2)
    return prod + tuple((p[::-1] for p in prod))

Granted, this makes use of generator expressions, so would have used more advanced ideas than would have been presented at that point in the OP's study, but is easily reformulated analogously with list comprehensions instead, had those been presented at that time, like this:

def cartesian_product_and_inverse2(tup1, tup2):
    prod = tuple([(t1, t2) for t1 in tup1 for t2 in tup2])
    return prod + tuple([p[::-1] for p in prod])

Answer 3

Mathematically cartesian product is defined as:

$$ A * B = \{(x, y)\ |\ x \in A\ \land\ y \in B\} $$

Reading in English it would be:

the cartesian product AxB is equal to the set of tuples (x, y) given that x is in A and y is in B.

Python is great because the syntax is much like the same, given two sets A and B:

A = {1, 2}
B = {3, 4}

The cartesian product A x B, will be:

AxB = {(x,y) for x in A for y in B}