how to convert a function into generator?

[=?ISO-8859-1?Q?Sch=FCle_Daniel?=]

Hello,

I came up with this algorithm to generate all permutations
it's not the best one, but it's easy enough

# lst = list with objects
def permute3(lst):
tmp = []
lenlst = len(lst)
def permute(perm, level):
if level == 1:
tmp.append(perm)
return
for i in lst:
if i not in perm:
permute(perm + (i,), level - 1)
for item in lst:
permute((item,), lenlst)
return tuple(tmp)

now I want to make a generator from it
the idea is to get each time a new permutation
I don't really understand how to handle the case
when my function has an inner function which has
a yield statement ..
I would say that the inner function becomes an generator
and stops&yields the value on each yield .. but in reality
I want to propogate these values to the caller of the outer function
I hope you got the idea of what I mean
the code is the sketch of the idea

def permute3gen(lst):
lenlst = len(lst)
def permute(perm, level):
if level == 1:
yield perm
return # not sure return without a value is allowed,
theoretically it could be replaces with if/else block
for i in lst:
if i not in perm:
permute(perm + (i,), level - 1)
for item in lst:
yield permute((item,), lenlst) # makes generator from the outer
function too


this is what I get

In [67]: reload permute
-------> reload(permute)
Out[67]: <module 'permute' from 'permute.pyc'>

In [68]: p = permute.permute3gen(["a","b","c","d"])

In [69]: p
Out[69]: <generator object at 0x2af3a44795f0>

In [70]: x = p.next()

In [71]: y = p.next()

In [72]: x
Out[72]: <generator object at 0x2af3a448e830>

In [73]: y
Out[73]: <generator object at 0x2af3a448e878>

In [74]: x.next()
---------------------------------------------------------------------------
<type 'exceptions.StopIteration'> Traceback (most recent call last)

/pool/PROG/python/permute/<ipython console> in <module>()

<type 'exceptions.StopIteration'>:

I don't understand why the generator x raises StopIteration exception
I would expect that x.next() would call
permute(("a",), 4) and would stop at "abcd"

thanks in advance

regards, Daniel

 

[Carsten Haese]

def permute3gen(lst):
lenlst = len(lst)
def permute(perm, level):
if level == 1:
yield perm
return # not sure return without a value is allowed,
theoretically it could be replaces with if/else block
for i in lst:
if i not in perm:
permute(perm + (i,), level - 1) ##1##
for item in lst:
yield permute((item,), lenlst) # makes generator from the outer
function too ##2##

Your only problem is in knowing what to do with recursively invoked
sub-generators. You have two such invocations, which I marked above with
##1## and ##2##, and neither one is handled correctly.

In ##1##, you construct a sub-generator and simply discard it. In ##2##,
you construct a sub-generator, and yield it (instead of yielding its
elements). In neither case do you actually consume any of the elements
that the sub-generators are prepared to produce.

To usefully invoke a sub-generator, you need to consume it (i.e. iterate
over it) and yield whatever it produces.

Hope this helps,

Carsten