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/)