ваш код - неорганизованная путаница. я не могу сказать, что он должен делать в деталях. если бы вы были более осторожны (аккуратнее, понятнее), то вам, вероятно, также было бы легче провести рефакторинг.
в любом случае, это может сделать что-то вроде того, что вы хотите:
from collections import defaultdict
def expand(line, links, known):
print 'expand'
known.append(line)
for child in links[line[-1]]:
newline = line + child
yield expand(newline, links, known)
def trampoline(generator):
stack = [generator]
while stack:
try:
generator = stack.pop()
print 'next'
child = next(generator)
stack.append(generator)
stack.append(child)
except StopIteration:
pass
def main(pairs):
have_successors = set()
links = defaultdict(lambda: set())
for (start, end) in pairs:
have_successors.add(start)
links[end].add(start)
known = []
for node in set(links.keys()):
if node not in have_successors:
trampoline(expand(node, links, known))
for line in known:
print line
if __name__ == '__main__':
main([("L", "G"), ("A", "B"), ("B", "I"), ("B", "H"), ("B", "C"), ("F", "G"), ("D", "E"), ("D", "J"), ("E", "L"), ("C", "D"), ("E", "F"), ("J", "K")])
Я использовал python2.7 - в более ранних версиях вам может потребоваться заменить next(foo) на foo.__next__() или аналогичный.
при написании кода уборщика
Во-первых, я тоже программист-самоучка, который начинал как академик (астроном), так что я вас сочувствую. и если вы продолжите, вы можете догнать и пройти мимо многих «обученных» программистов. это не так сложно, как вы думаете ...
во-вторых, есть разница между использованием «уловок», таких как defaultdict, который является просто вопросом опыта / практики, и «аккуратностью». я не ожидаю, что вы узнаете о дефолте - это придет со временем.
но то, что вы должны сделать сейчас - это написать чистый, простой код:
Я думаю, что у вас есть комментарии о более ранних версиях кода. один упоминает «максимальную длину», но я не вижу никаких расчетов длины. поэтому либо комментарий устарел (в таком случае, почему он там есть), либо он должен быть более четким (почему эти вещи имеют максимальную длину?). в общем, вы должны комментировать как можно меньше, потому что в противном случае он устареет. но в то же время вы должны использовать комментарии, где неясно, какие «идеи» стоят за кодом. код должен говорить сам за себя, поэтому не говорите «я добавляю два числа здесь», но говорите «фрагменты здесь должны быть максимальной длины, потому что ...», если есть какая-то «скрытая» логика.
будьте осторожны с фотографиями, которые вы используете. по какой-то причине ваш код начинается с известных терминалов. Таким образом, вы строите вещи с конца обратно к началу. Зачем? это странный взгляд на проблему. Разве не было бы яснее начать с точек, которые находятся в начале, но не в конце? а затем использовать "startIDs", чтобы вырастить их? таким образом, вы "идете вперед". это может показаться мелочью, но это затрудняет чтение кода.
используйте правильные инструменты для работы. вы не использовали startID, так почему вы строите карту? все, что вам было нужно, это набор. возможно, вы не знали о сетах, и в этом случае все в порядке (но вы знаете сейчас!: o). но в остальном это тоже сбивает с толку - кто-то, читающий ваш код, ожидает, что вы делаете что-то по какой-то причине. поэтому, когда вы делаете больше, чем необходимо, они задаются вопросом, почему.
избегайте считать вещи, когда вам это не нужно. у вас есть i и index и count. они все нужны? эти виды счетчиков - самый простой способ иметь ошибки, потому что они могут иметь маленькие глупые логические ошибки. и они делают код неясным. if i < count - 1: действительно говорит "это последняя ветка"? если так, было бы намного лучше написать if branch == branches [-1]:, потому что это ясно о том, что вы думаете.
аналогично с циклическим выравниванием в main. использование i только усложняет ситуацию. вы обрабатываете каждое выравнивание, поэтому просто скажите for each alignment in alignments. если это дает ошибку из-за изменения выравнивания, сделайте неизменную копию: for each alignment in list(alignments).
избегайте особых случаев, если они не нужны. в buildAlignment у вас есть тест в самом начале для особого случая. но действительно ли это было нужно? Вы бы получили тот же результат без него? часто, когда вы пишете код просто, оказывается, что вам не нужны особые случаи. в моем коде мне не нужно проверять, есть ли одна или нет "ссылки", потому что он работает нормально во всех этих случаях. это дает вам меньше кода и меньше поводов для беспокойства и меньше шансов на ошибки.
больше, чем все эти вещи - вы должны быть одержимо аккуратными и методичными . у вас много идей, но вместо того, чтобы попробовать половину одного, затем перейти к другому, записать их и проработать их один за другим. в противном случае вы получите беспорядок и код, который вы не понимаете. сначала кажется, что вы теряете время, но начинаете понимать, что в результате вы становитесь быстрее, потому что проводите меньше времени в замешательстве ...
на генераторах
[я немного изменил код, чтобы выделить newline и добавить print в нескольких местах.]
сначала вы запустили код? это делает то, что вы хотите? Вы видите, как это связано с тем, что у вас было раньше? мой expand похож на ваш buildAlignment (надеюсь).
если вы запустите его (последняя версия), вы увидите:
: python2.7 recurse.py
next
expand
next
expand
next
expand
next
expand
next
expand
next
expand
next
expand
next
next
...
, который может дать подсказку о том, что происходит. «хитрость» - это выражение yield - компилятор python видит это и вместо обычной функции создает генератор .
генератор - очень странная вещь. это в основном ваша функция (в данном случае expand), «связанная», чтобы ее можно было выполнять поэтапно. работа выполняется с помощью next(), и функция останавливается снова каждый раз, когда достигается yield.
так trampoline пропущен этот странный комплект. и это вызывает next(). это «волшебная» функция, которая запускает функцию. поэтому, когда вызывается next, функция начинает работать, пока не достигнет yield, где она возвращает новый пакет. команда trampoline() затем сохраняет старый пакет и начинает работать с новым, вызывая next(), запуская его ... и т. д. и т. д.
когда у генератора "не хватает дел", он поднимает StopIteration. поэтому, когда мы достигаем точки, когда выражение больше не может расти, мы видим это исключение в trampoline(). в этот момент мы возвращаемся к последнему «старому» пакету (хранящемуся в нашем stack) и снова вызываем next(). этот пакет перезапускает с того места, где он находился (сразу после yield), и продолжает, вероятно, делая еще один цикл в while, пока он снова не достигнет yield (или не закончится и не повысит StopIteration) .
так, в конце концов, код делает то же самое, как если бы yield там не было! единственное отличие состоит в том, что мы продолжаем делать эти связки и возвращать их. что кажется бессмысленным. за исключением того, что мы больше не используем стек! поскольку пакет возвращается , стек не "используется"! вот почему нам нужно управлять собственным стеком (список stack), иначе невозможно узнать, каким был предыдущий вызов.
хорошо, хорошо, я не ожидаю, что вы это вообще поймете. да, это безумие Теперь вам нужно уйти и поискать "генераторы Python". и написать свой собственный код, чтобы проверить его. но, надеюсь, это укажет путь.
о, я тоже думал прошлой ночью. и я подозреваю, что если вы исчерпали стек, это было на самом деле потому, что у вас есть петли, а не потому, что цепи очень длинные. Вы рассматривали петли? A-> B, B-> C, C-> A, ....