How to convert recursive function to generator?

Question

I have the following recursive function to generate a list of valid configurations for a (named) list of positions, where each position can be used only once:

def generate_configurations(configurations, named_positions, current):
    if len(current) == len(named_positions):
        configurations.append(current)
        return configurations

    name, positions = named_positions[len(current)]
    for x in positions:
        if x not in current:
            generate_configurations(configurations, named_positions, current + (x,))

    return configurations

Here is an example of how I call it:

named_positions = [('a', [0,1,2]),
                   ('b', [1,3]),
                   ('c', [1,2])]

for comb in generate_configurations([], named_positions, ()):
    print comb

Which gives the following output:

(0, 1, 2)
(0, 3, 1)
(0, 3, 2)
(1, 3, 2)
(2, 3, 1)

Also, it is possible there are no valid combinations, e.g. for named_positions = [('a', [3]), ('b', [3])].

Now depending on the input named_positions, the configurations list can quickly become huge, resulting in a MemoryError. I believe this function could be re-written as a generator, so I tried the following:

def generate_configurations(named_positions, current):
    if len(current) == len(named_positions):
        yield current

    name, positions = named_positions[len(current)]
    for x in positions:
        if x not in current:
            generate_configurations(named_positions, current + (x,))

named_positions = [('a', [0,1,2]),
                   ('b', [1,3]),
                   ('c', [1,2])]

for comb in generate_configurations(named_positions, ()):
    print comb

but this doesn't generate any results at all. What am I doing wrong?

ShadowRanger · Accepted Answer · 2015-11-10 02:53:00Z

1

You need to yield up the recursive call stack or the inner yields never happen and get discarded. Since this is tagged Python 2.7, the recursive calls would be handled by changing:

if x not in current:
    # Creates the generator, but doesn't run it out to get and yield values
    generate_configurations(named_positions, current + (x,))

to:

if x not in current:
    # Actually runs the generator and yields values up the call stack
    for y in generate_configurations(named_positions, current + (x,)):
        yield y

In Python 3.3 and higher, you can delegate directly with:

if x not in current:
    yield from generate_configurations(named_positions, current + (x,)):

answered Nov 10, 2015 at 2:53

ShadowRanger

158k12 gold badges221 silver badges315 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

FriendFX Over a year ago

Thanks, that works now - I also had to add a return statement just after yield current to avoid it recursing further than it should.

Strikeskids · Accepted Answer · 2015-11-10 02:53:01Z

1

When you are using generators, you need to make sure that your sub-generator recursive calls pass back up to the calling method.

def recur_generator(n):
    yield my_thing
    yield my_other_thing
    if n > 0:
        yield from recur_generator(n-1)

Notice here that the yield from is what passes the yield calls back up to the parent call.

You should change the recursive call line to

yield from generate_configurations(named_positions, current + (x,))

Otherwise, your generator is fine.

EDIT: Didn't notice that this was python2. You can use

for x in recur_generator(n-1):
    yield x

instead of yield from.

answered Nov 10, 2015 at 2:53

Strikeskids

4,08215 silver badges27 bronze badges

Collectives™ on Stack Overflow

How to convert recursive function to generator?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related