More user feedback on Sets.py
David Eppstein
eppstein at ics.uci.edu
Sun Nov 9 18:20:14 EST 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