More user feedback on

David Eppstein eppstein at
Mon Nov 10 00:20:14 CET 2003

In article <eppstein-5A1CB4.15023909112003 at>,
 David Eppstein <eppstein at> wrote:

> def powerset(U):
>     """Generates all subsets of a set or sequence U."""
>     U = iter(U)
>     try:
>         x = ImmutableSet([])
>         for S in powerset(U):
>             yield S
>             yield S | x
>     except StopIteration:
>         yield ImmutableSet()

By the way, I realized later that a little modification of this nethod 
allows powerset to work with infinite sequences:

def powerset(U):
    """Generates all subsets of a set or sequence U.
    U may be infinite, in which case the powerset is
    also infinite, and the first 2^i items generated
    will be the sets of the first i items in U.
    U = iter(U)
    yield ImmutableSet()
    x = ImmutableSet([])
    yield x
    it = powerset(U)   # skip empty set, already generated
    for S in it:
        yield S
        yield S | x        

I am a little concerned that "powerset" is not the right name, because 
its output is a sequence not a set, but can't think of a better.

David Eppstein            
Univ. of California, Irvine, School of Information & Computer Science

More information about the Python-list mailing list