Is there way to turn list of answers from script as yielded values?

Question

I have long running program that I want to keep responsive. The algorithm is recursive, so sometimes even the sub-tasks in longer running calls can be longer than shorter whole runs. I have tried to make it to use yield but only ended up with list full of generators in various levels of recursive list structure (list also multilevel hierarchy, recording depth of calls). I finally made simple print the answers version, but it prints the answers in the end. I must not print the recursive calls results only, also the results need post processing before printing.

Is there simple pattern to make top level function call to yield values, but recursive calls to return the answers? Should I use for loops over recursive call results or make list() of the aswers from recursive calls? Should I just put depth parameter and return with depth > 0 and yield at depth 0?

Anyway, is there easy way to turn one answer per line outputing call to yield the lines back to main Python program? Or should I still return the full list from module call? I could easily run the os call version in separate interpreter with 'bg' in Linux system couldn't I?

The problem is complete covering problem, an example useful to my application would be for example to do same as this without the combinations, only adding numbers until they go over the limit recursively returning the exact sums:

from __future__ import print_function
def subset(seq, mask):
    """ binary mask of len(seq) bits, return generator for the sequence """
    return (c for ind,c in enumerate(seq) if mask & (1<<ind))

numbers = [1, 5, 3, 9, 4]
print('Numbers: ',numbers)
print('Possible sums',min(numbers),'..',sum(numbers))

for i in range(1,2**len(numbers)):
    sub = list(subset(numbers, i))
    print(sum(sub),'=',' + '.join(str(s) for s in sub))

print()
target = 11
print ('Finding subsequence for sum = %i' % target)

check = None
for check in (subset(numbers, mask)
              for mask in range(1,2**len(numbers))
              if sum(subset(numbers, mask))==target):
    print (' + '.join(str(s) for s in check), ' = ', target)
if not check:
    print('No solutions')

Answer 1

You're a little bit short on details of what you're actually trying to do, but here's my best guess (note: you'll need Python 2.6):

def do_stuff(num):
    children = [ _do_stuff(x + 1) for x in range(num) ]
    for child in children:
        child.send(None)

    count = 0
    while children:
        child = children.pop(0)
        try:
            count += child.send(count)
        except StopIteration:
            continue
        children.append(child)

def _do_stuff(num):
    to_add = 0
    for x in range(num):
        from_parent = (yield (to_add + x))
        print "child %s got %s" %(num, from_parent)
        to_add += from_parent

Which will work like this:

>>> do_stuff(3)
child 1 got 0
child 2 got 0
child 3 got 1
child 2 got 3
child 3 got 3
child 3 got 9

Sorry that this example is a bit confusing — my brain isn't up to coming up with a better example right now.

Also, some notes: * The children could yield another generator, which could be added to the list of children * This implementation is slow (popping from the head of a list requires O(n) time) — see dequeue module * The child.send(None) is needed to "prime" the generators (that is, execute up to the first yield)

Answer 2

Your question isn't very clear. Maybe this will help.

Making a recursive generator is straightforward; the function just has to iterate over itself instead of call itself. For instance, if you wanted to write a generator that flattened a tree, it might look like this:

def descendants(node):
   for child in children(node):
      yield child
      for descendant in descendants(child):
         yield descendant

This approach is returning each descendant node to the caller as it is found. If, for some reason, the children function were itself a generator that took a whole second to return each node, the descendants function would return a descendant node to its caller once a second.

This all assumes that the process is synchronous. If it is (or can be made to be) asynchronous, you have a very different problem that requires a very different approach. You can wrap an asynchronous process in a generator that yields results as they become available; if you do this, every call to the generator will block and wait until a background thread (or process) produces whatever next result is available. This provides a simple facade to hide the complexities of asynchronous code behind; the caller just does:

for x in get_things(param):
   print x

and the get_things() function creates threads (or processes) and yields the objects as the threads return them.

How the get_things() function does this is, of course, a big question, and totally dependent on what your problem actually is.