"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 -- http://mail.python.org/mailman/listinfo/python-list