[Python-Dev] Re: PEP 218 (sets); moving set.py to Lib

[Guido van Rossum]

> It should have powerset and cartesian-product methods.  Shall I code
> them?

The Cartesian product of two sets is easy:

def product(s1, s2):
    cp = Set()
    for x in s1:
        for y in s2:
            cp.add((x, y))
    return cp

But I'm not sure if this is useful enough to add to the set class --
it seems a great way to waste a lot of memory, and typical uses are
probably better served by writing out the for-loops.  Perhaps this
could be coded as a generator though.

More fun would be the cartesian product of N sets; I guess it would
have to be recursive.  Here's a generator version:

def product(s, *sets):
    if not sets:
        for x in s:
            yield (x,)
    else:
        subproduct = list(product(*sets))
        for x in s:
            for t in subproduct:
                yield (x,) + t

Note that this doesn't require sets; its arguments can be arbitrary
iterables.  So maybe this belongs in a module of iterator utilities
rather than in the sets module.  API choice: product() with a single
argument yields a series of 1-tuples.  That's slightly awkward, but
works better for the recursion.  And specifically asking for the
Cartesian product of a single set is kind of pointless.

If we *do* add this to the Set class, it could be aliased to __mul__
(giving another reason why using * for set intersection is a bad
idea).

Here's a naive powerset implementation returning a set:

def power(s):
    ps = Set()
    ps.add(ImmutableSet([]))
    for elt in s:
        s1 = Set([elt])
        ps1 = Set()
        for ss in ps:
           ps1.add(ss | s1)
        ps |= ps1
    return ps

This is even more of a memory hog; however the algorithm is slightly
more subtle so it's perhaps more valuable to have this in the library.

Here's a generator version:

def power(s):
    if len(s) == 0:
        yield Set()
    else:
        # Non-destructively choose a random element:
        x = Set([iter(s).next()])
        for ss in power(s - x):
            yield ss
            yield ss | x

I'm not totally happy with this -- it recurses for each element in s,
creating a new set at each level that is s minus one element.  I'd
prefer to build the set up from the other end, like the first
version.

IOW I'd love to see your version. :-)

The first power() example raises a point about the set API: the Set()
constructor can be called without an iterable argument, but
ImmutableSet() cannot.  Maybe ImmutableSet() should be allowed too?
It creates an immutable empty set.  (Hm, this could be a singleton.
__new__ could take care of that.)

While comparing the various versions of power(), I also ran into an
interesting bug in the code.  While Set([1]) == ImmutableSet([1]),
Set([Set([1])]) != Set([ImmutableSet([1])]).  I have to investigate
this.

--Guido van Rossum (home page: http://www.python.org/~guido/)