[Python-Dev] Re: PEP 218 (sets); moving set.py to Lib
Guido van Rossum
guido@python.org
Tue, 20 Aug 2002 22:25:17 -0400
> 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/)