Recursive generators and backtracking search

[George Sakkis]

"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]:
            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