"Talin" <[EMAIL PROTECTED]> wrote:
> I've been using generators to implement backtracking search for a while
> now. Unfortunately, my code is large and complex enough (doing
> unification on math expressions) that its hard to post a simple
> example. So I decided to look for a simpler problem that could be used
> to demonstrate the technique that I am talking about.
Here are two even simpler problems that are solved elegantly (though
not necessarily efficiently) with recursive generators:
def cartesian_product(*sequences):
'''Iterate over the elements of the cartesian product of zero or
more sequences.
>>> for x in cartesian_product(range(3), 'a', (3.25,-1.2)):
... print x
(0, 'a', 3.25)
(0, 'a', -1.2)
(1, 'a', 3.25)
(1, 'a', -1.2)
(2, 'a', 3.25)
(2, 'a', -1.2)
'''
if not sequences:
yield ()
else:
for item in sequences[0]:
head = (item,)
for tail in cartesian_product(*sequences[1:]):
yield head + tail
def powerset(iterable):
'''Iterate over all subsets of an iterable.
>>> for s in powerset('abc'):
... print s
frozenset([])
frozenset(['a'])
frozenset(['b'])
frozenset(['a', 'b'])
frozenset(['c'])
frozenset(['a', 'c'])
frozenset(['c', 'b'])
frozenset(['a', 'c', 'b'])
'''
yield frozenset()
for s in _powerset(iter(iterable)):
yield s
def _powerset(iterator):
first = frozenset([iterator.next()])
yield first
for s in _powerset(iterator):
yield s
yield s | first
George
--
http://mail.python.org/mailman/listinfo/python-list
