# Recursive generators and backtracking search

George Sakkis gsakkis at rutgers.edu
Sun Oct 30 02:35:53 CEST 2005

```"Talin" <viri... at gmail.com> 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]:
for tail in cartesian_product(*sequences[1:]):

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

```