help with generators

[Mayer]

Hello:

I need some help in understanding generators. I get them to work in
simple cases, but the following example puzzles me. Consider the
non-generator, "ordinary" procedure:

def foo(n):
s = []
def foo(n):
if n == 0:
print s
else:
s.append(0)
foo(n - 1)
s.pop()
s.append(1)
foo(n - 1)
s.pop()
foo(n)

foo(n) prints all n-bit-wide binary numbers as a list. I would now like
to create a generator for such numbers:

def bin(n):
s = []
def bin(n):
if n == 0:
yield s
else:
s.append(0)
bin(n - 1)
s.pop()
s.append(1)
bin(n - 1)
s.pop()
return bin(n)

yet this doesn't work as expected. Can someone please explain why?

Thanks,

Mayer Goldberg

 

[Steven Bethard]

Hello:

I need some help in understanding generators. I get them to work in
simple cases, but the following example puzzles me. Consider the
non-generator, "ordinary" procedure:

def foo(n):
s = []
def foo(n):
if n == 0:
print s
else:
s.append(0)
foo(n - 1)
s.pop()
s.append(1)
foo(n - 1)
s.pop()
foo(n)

foo(n) prints all n-bit-wide binary numbers as a list. I would now like
to create a generator for such numbers:

def bin(n):
s = []
def bin(n):
if n == 0:
yield s
else:
s.append(0)
bin(n - 1)
s.pop()
s.append(1)
bin(n - 1)
s.pop()
return bin(n)

yet this doesn't work as expected. Can someone please explain why?

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

 

[George Sakkis]

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

 

[Mayer]

Thanks a lot! This clarified [I think] my misunderstanding about yield,
and I also learned something about efficiency from George's code --
Thanks.

So, The function tel(aString) takes a string (or a number) that denote
a phone number, using digits or letters, and returns a generator for
the set of all possible words that are made up of that phone number.
It's not a terribly useful program, but it's short and it's a lot of
fun.

Mayer

import string

def addKeyString(keyString):
for ch in keyString:
keypad[ch] = keyString

keypad = {}
addKeyString('0')
addKeyString('1')
addKeyString('2ABC')
addKeyString('3DEF')
addKeyString('4GHI')
addKeyString('5JKL')
addKeyString('6MNO')
addKeyString('7PQRS')
addKeyString('8TUV')
addKeyString('9WXYZ')

def tel(phone):
phoneString = str(phone)
length = len(phoneString)
buffer = [Null] * length
def run(n):
if n == length:
yield string.join(buffer, '')
else:
for word in run(n + 1):
for letter in keypad[phoneString[n]]:
buffer[n] = letter
yield buffer
return run(0, '')

 

[Steven Bethard]

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)
...

[snip]
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.

Yup. However, this was the most direct translation of the OP's original
function (which also only had a single list). Since the question was
about how generators worked, I figured the most direct translation would
probably be the most useful response.

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 []

This is definitely the way I would have written it.

STeVe