More user feedback on Sets.py

David Eppstein eppstein at ics.uci.edu
Mon Nov 10 00:20:14 CET 2003


In article <eppstein-5A1CB4.15023909112003 at news.service.uci.edu>,
 David Eppstein <eppstein at ics.uci.edu> wrote:

> def powerset(U):
>     """Generates all subsets of a set or sequence U."""
>     U = iter(U)
>     try:
>         x = ImmutableSet([U.next()])
>         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([U.next()])
    yield x
    it = powerset(U)
    it.next()   # 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                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science




More information about the Python-list mailing list