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?
(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