Some thougts on cartesian products

mensanator at mensanator at
Mon Jan 23 17:26:23 EST 2006

Steven D'Aprano wrote:
> On Mon, 23 Jan 2006 18:17:08 +0000, Bryan Olson wrote:
> > Steven D'Aprano wrote:
> >> Bryan Olson wrote:
> >>
> >>
> > [Christoph Zwerschke had written:]
> >>>>What I expect as the result is the "cartesian product" of the strings.
> >>>
> >>>There's no such thing; you'd have to define it first. Are duplicates
> >>>significant? Order?
> >>
> >>
> >> Google "cartesian product" and hit "I'm feeling lucky".
> >>
> >> Or go here:
> >>
> >> Still think there is no such thing?
> >
> > Uh, yes.
> >
> >     The Cartesian product of two sets A and B (also called the
> >     product set, set direct product, or cross product) is defined to
> >     be the set of [...]
> >
> > All sets, no strings. What were you looking at?
> You've just quoted a definition of Cartesian product [yes, you are right
> about capitalisation, my bad]. How can you say with a straight face that
> there is no such thing as a Cartesian product?
> The question of sets versus strings is a red herring. Addition, in
> mathematics, is defined on reals. No computer yet made can do addition on
> reals. Should you declare that there is no such thing as addition because
> reals and floats are different?
> If people wish to extend Cartesian products to work on sequences, not just
> sets, then to my mind that's a pretty obvious and sensible generalisation.

I use Cartesian Products all the time in MS-Access, typically the
product of a set (of records) with itself. I really like your generator
because I can now do this stuff directly in Python. And I usually
want just a subset of the Cartesian Product, so I modified your
generator to produce what I want:

def cartprod(A, B, perm=True, repl=True):
    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:
	    if perm and repl:              # permutation with replacement
	        yield convert((a, b))
	    if (not perm) and repl:        # combination with replacement
		if b>=a:
		    yield convert((a,b))
	    if perm and (not repl):        # permutation w/o  replacement
		if b!=a:
		    yield convert((a,b))
	    if (not perm) and (not repl):  # combination w/o  replacement
		if b>a:
		    yield convert((a,b))

print 'For "abc"x"abc":'

cprods = cartprod("abc", "abc", True, True)
print 'permutation with replacement', list(cprods)

cprods = cartprod("abc", "abc", False, True)
print 'combination with replacement', list(cprods)

cprods = cartprod("abc", "abc", True, False)
print 'permutation w/o  replacement', list(cprods)

cprods = cartprod("abc", "abc", False, False)
print 'combination w/o  replacement', list(cprods)


For "abc"x"abc":

permutation with replacement ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca',
'cb', 'cc']

combination with replacement ['aa', 'ab', 'ac', 'bb', 'bc', 'cc']

permutation w/o  replacement ['ab', 'ac', 'ba', 'bc', 'ca', 'cb']

combination w/o  replacement ['ab', 'ac', 'bc']


Thanks for showing me an easy way to do this.

> -- 
> Steven.

More information about the Python-list mailing list