0
\$\begingroup\$

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?

\$\endgroup\$
  • 2
    \$\begingroup\$ Either the problem description, or the example code, is mistaken: (4, 1) is not a member of the Cartesian product of (1, 2) and (4, 5). \$\endgroup\$ – Gareth Rees Apr 14 '15 at 10:14
  • \$\begingroup\$ I've rewritten the question to explain more clearly where the constraints comes from, and added the homework and reinventing-the-wheel tags \$\endgroup\$ – Gareth Rees Apr 14 '15 at 10:19
  • \$\begingroup\$ @GarethRees am not sure, what you mean by lectrue_3? lecture 9 is about sequence taught by Professor. Discussion 3 is part of exercise that is between mentor and students. Professor is not part of this. \$\endgroup\$ – overexchange Apr 14 '15 at 10:32
  • \$\begingroup\$ Sorry if I misunderstood. \$\endgroup\$ – Gareth Rees Apr 14 '15 at 10:34
  • 2
    \$\begingroup\$ @GarethRees I don't think the -1 is justified, the OP put the problem exactly as it is in the coursework pdf. The error is not the OP's fault, it's the fault of whoever created the Berkeley CS coursework. \$\endgroup\$ – Snowbody Apr 14 '15 at 15:10
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ may be, recursive version looks unstructured to me. Can I see like if..elif..elif..else? we are yet to learn purpose of yield. \$\endgroup\$ – overexchange Apr 14 '15 at 14:38
  • \$\begingroup\$ I have added a second recursive implementation that is like you requested. I don't know what you have learned yet, so I don't really know what types of implementations to avoid. \$\endgroup\$ – TheBlackCat Apr 14 '15 at 14:53
  • \$\begingroup\$ Can we define algorithmic logic behind such recursive style? Because min_element_recur had an algorithmic logic of dropping elements until you are left with just one which makes it more verbose. After debugging your code, I feel that you wrote this recursive code driven by flow of cartesian operation? That is why, cartesian_product_recursive_2 also looks less verbose. One reason for this recursive solution to be less verbose is because recursive approach is not the right approach to solve this problem? Am I correct? \$\endgroup\$ – overexchange Apr 16 '15 at 1:19
  • \$\begingroup\$ I think the algorithmic logic is something like get the current item from tup1, and combine it with each item from tup2 until there are none left, then move on to the next item of tup1, make it the current item, and repeat until there are no more items in tup1. There are two majors problems with this approach. First, it is slower in languages like python due to the function call overhead. Second, since slicing tuples makes a copy, you will end up with more memory usage. And I wouldn't say it is less verbose, on the contrary it uses more characters than the looping version. \$\endgroup\$ – TheBlackCat Apr 16 '15 at 14:26
3
\$\begingroup\$

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])
\$\endgroup\$
1
\$\begingroup\$

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}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.