Как преобразовать рекурсивную функцию в генератор?

Question

Я имею следующую рекурсивную функцию, чтобы сгенерировать список допустимых конфигураций для (имени) список позиций, где каждая позиция может быть использована только один раз:

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 

Вот пример того, как я это называю:

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

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

что дает следующий результат:

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

Кроме того, можно есть нет действительных комбинаций, например. для named_positions = [('a', [3]), ('b', [3])].

Теперь, в зависимости от ввода named_positions, список configurations может быстро стать огромным, в результате получится MemoryError. Я считаю, что эта функция может быть переписана как генератор, поэтому я попытался следующее:

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 

, но это не приносит никаких результатов вообще. Что я делаю не так?

Answer 1

Необходимо, чтобы рекурсивный стек вызовов или внутренний yield не произошли и отброшены. Так как это помечено Python 2.7, рекурсивные вызовы будут обрабатываться изменения:

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

к:

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 

В Python 3.3 и выше, вы можете делегировать непосредственно:

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

Answer 2

Когда вы используете генераторы, вам необходимо убедиться, что рекурсивные вызовы вашего подгенератора возвращаются к вызывающему методу.

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

Обратите внимание, что здесь yield from является то, что проходит выход перезванивает до родительского вызова.

Вы должны изменить рекурсивную телефонную линию к

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

В противном случае, ваш генератор отлично.

EDIT: Не заметил, что это был python2. Вы можете использовать

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

вместо yield from.