help with generators

[George Sakkis]

"Steven Bethard" wrote:

> It would help if you explained what you expected.  But here's code
that
> prints about the same as your non-generator function.
>
> py> def bin(n):
> ...     s = []
> ...     def bin(n):
> ...         if n == 0:
> ...             yield s
> ...         else:
> ...             s.append(0)
> ...             for s1 in bin(n - 1):
> ...                 yield s1
> ...             s.pop()
> ...             s.append(1)
> ...             for s1 in bin(n - 1):
> ...                 yield s1
> ...             s.pop()
> ...     return bin(n)
> ...
> py> for s in bin(1):
> ...     print s
> ...
> [0]
> [1]
> py> for s in bin(2):
> ...     print s
> ...
> [0, 0]
> [0, 1]
> [1, 0]
> [1, 1]
>
> Note that to make the recursive calls work, you *must* iterate
through
> them, thus what was in your code:
>
>      bin(n - 1)
>
> now looks like:
>
>      for s1 in bin(n - 1):
>          yield s1
>
> This is crucial.  bin(n - 1) creates a generator object.  But unless
you
> put it in a for-loop (or call it's .next()) method, the generator
will
> never execute any code.
>
> HTH,
>
> STeVe


A caveat of the implementation above: it yields the same instance (s),
which is unsafe if the loop variable is modified (e.g. in the "for s in
bin(n)" loop, s should not be modified). Moreover, each yielded value
should be 'consumed' and then discarded; attempting to store it (as in
list(bin(n))) references only the last yielded value.

Here's a shorter, clear and safe implementation:

def bin2(n):
    if n:
        for tail in bin2(n-1):
            yield [0] + tail
            yield [1] + tail
    else:
        yield []

It also turns out to be faster than the original despite yielding a new
list every time:
$ python /usr/local/lib/python2.4/timeit.py -s "from bin import bin"
"for i in bin(10): pass"
100 loops, best of 3: 5.21 msec per loop
$ python /usr/local/lib/python2.4/timeit.py -s "from bin import bin2"
"for i in bin2(10): pass"
100 loops, best of 3: 2.68 msec per loop

The reason is that the original computes the same permutations ("for s1
in bin(n - 1)") twice. Here's a faster version that preallocates the
list and sets the 0s and 1s for each permutation:

def bin3(n):
    array = [None]*n
    def _bin(n):
        if not n:
            yield array
        else:
            n -= 1
            for perm in _bin(n):
                # replace 'yield perm' with 'yield list(perm)' for safe
                # mutation and accumulation of yielded lists
                perm[n] = 0; yield perm
                perm[n] = 1; yield perm
    return _bin(n)

$ python /usr/local/lib/python2.4/timeit.py -s "from bin import bin3"
"for i in bin3(10): pass"
1000 loops, best of 3: 587 usec per loop

Cheers,
George