Рекурсивные генераторы в Python

я написал функцию, возвращающую генератор, содержащий каждую уникальную комбинацию вложенных-строк заданной длины, содержащих более n элементов из первичной строки.

В качестве иллюстрации:

если у меня есть 'abcdefghi' и зонд длины два, а также порог в 4 элемента на список, который я хотел бы получить:

['ab', 'cd', 'ef', 'gh']
['ab', 'de', 'fg', 'hi']
['bc', 'de', 'fg', 'hi']

Моя первая попытка решить эту проблему заключалась в возврате списка списков. Это привело к переполнению памяти компьютера. В качестве грубого вторичного решения я создал генератор, который делает что-то подобное. Проблема в том, что я создал вложенный генератор, который вызывает сам себя. Когда я запускаю эту функцию, кажется, что она просто зацикливается на внутреннем цикле for, фактически не вызывая себя снова. Я думал, что генератор будет опережать рекурсивную дыру настолько далеко, насколько это необходимо, пока не попадет в оператор yield. Любая подсказка, что происходит?

def get_next_probe(self, current_probe_list, probes, unit_length):
    if isinstance(current_probe_list, list):
        last_probe=current_probe_list[-1]
        available_probes = [candidate for candidate in probes if candidate.start>last_probe.end]
    else:
        available_probes = [candidate for candidate in probes if candidate.start<unit_length]

    if available_probes:

        max_position=min([probe.end for probe in available_probes])
        available_probes2=[probe for probe in available_probes if max_position+1>probe.start]

        for new_last_probe in available_probes2:
            new_list=list(current_probe_list)
            new_list.append(new_last_probe)
            self.get_next_probe(new_list, probes, unit_length)

    else:
        if len(current_probe_list)>=self.num_units:
            yield current_probe_list

Если yield изменен на print, все работает отлично! Я был бы признателен за любую помощь, которую я мог бы получить. Я понимаю, что это не оптимальная реализация проблемы поиска такого типа, похоже, это возвращение списка найденных позиций из последнего вызова get_next_probe и фильтрация этого списка для элементов, которые не перекрываются new_last_probe.end был бы намного эффективнее... но мне было намного легче написать его. Любой ввод алгоритма все равно будет оценен.

Спасибо!

9
задан inspectorG4dget 22 April 2012 в 02:27
поделиться