Some thougts on cartesian products

Steven D'Aprano steve at
Sun Jan 22 14:50:13 EST 2006

On Sun, 22 Jan 2006 19:12:49 +0100, Christoph Zwerschke wrote:

> Steven D'Aprano wrote:
>> On Sun, 22 Jan 2006 18:29:45 +0100, Christoph Zwerschke wrote:
>>> For doing such things I would use a vector subtype of list.
>> Not everything needs to be a separate class! Why create a magic class for
>> every piece of functionality you want? Just create functions that operate
>> on existing classes!
>  >
>  > What advantage is there to creating a "list with cartesian product"
>  > subclass of list?
> Principally, you're right (see also my example with iterators).
> But I can still see two reasons for classes:
> 1) That function would have to make a lot of case distinctions (check 
> the types of operands). If you have a class, you already know the type 
> of the operands (at least one).

If you are happy to always return a list of tuples regardless of what the
two operands are, generators make it so easy it is shameful. Even if you
want a special case of two string arguments returning a string, it is
hardly any more difficult:

def cartprod(A, B):
    if type(A) == type(B) == str:
        convert = lambda obj: "".join(list(obj))
        convert = lambda obj: obj  # do nothing
    for a in A:
        for b in B:
            yield convert((a, b))

Notice that the *only* reason we look at the type of the arguments is
because we want two strings to return a string. If we don't care about
that, the generator is less than half the size:

def cartprod(A, B):
    for a in A:
        for b in B:
            yield (a, b)

That's a generator giving you the products one at a time. For the
benefit of anyone out there who doesn't know about generators, you use it
like this:

>>> cprods = cartprod([1,2,3], "abc")
>>> for t in cprods:
...     print t
(1, 'a')
(1, 'b')
(2, 'a')
(2, 'b')
(3, 'a')
(3, 'b')

If you want them all at once, memory allowing, you do this:

>>> cprods = cartprod([1,2,3], "abc")
>>> list(cprods)
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]

> 2) It allows you to write a*b instead of mul(a,b) which looks nicer.

But not as clear as cartprod(a,b) or even cartesian_product(a,b).


More information about the Python-list mailing list