ID ペアのリスト ([("A","B"),("B","C"),("C","D"),...]) とシーケンスを読み取る関数を作成しました。ブランチを含む ID の最初から最後まで。
順序付けられた ID の各リストは、Alignment と呼ばれるクラスに保持されます。この関数は、再帰を使用して、ブランチがメイン リストから分岐する ID から始まる新しいアライメントを作成することにより、ブランチを処理します。
特定の入力を使用すると、Python によって設定された最大再帰制限に達する可能性があることがわかりました。sys.setrecursionlimit() を使用してこの制限を増やすことができることはわかっていますが、可能な分岐の組み合わせの数がわからないため、この戦術は避けたいと思います。
再帰関数を反復関数に変換することに関するいくつかの記事を読みましたが、再帰は関数の途中で行われ、指数関数的になる可能性があるため、この特定の関数を処理する最良の方法を決定できませんでした。
どなたかご提案いただけますか？
ありがとう、ブライアン
コードは以下に掲載されています。
def buildAlignments(alignment, alignmentList, endIDs):
while alignment.start in endIDs:
#If endID only has one preceding ID: add preceding ID to alignment
if len(endIDs[alignment.start]) == 1:
alignment.add(endIDs[alignment.start][0])
else:
#List to hold all branches that end at spanEnd
branches = []
for each in endIDs[alignment.start]:
#New alignment for each branch
al = Alignment(each)
#Recursively process each new alignment
buildAlignments(al, branches, endIDs)
branches.append(al)
count = len(branches)
i = 0
index = 0
#Loop through branches by length
for branch in branches:
if i < count - 1:
#Create copy of original alignment and add branch to alignment
al = Alignment(alignment)
al += branch #branches[index]
alignmentList.append(al)
i += 1
#Add single branch to existing original alignment
else: alignment += branch #branches[index]
index += 1
def main():
IDs = [("L", "G"), ("A", "B"), ("B", "I"), ("B", "H"), ("B", "C"), ("F", "G"), ("D", "E"), ("D", "J"), ("E", "L"), ("C", "D"), ("E", "F"), ("J", "K")]
#Gather all startIDs with corresponding endIDs and vice versa
startIDs = {}
endIDs = {}
for pair in IDs:
if not pair[0] in startIDs: startIDs[pair[0]] = []
startIDs[pair[0]].append(pair[1])
if not pair[1] in endIDs: endIDs[pair[1]] = []
endIDs[pair[1]].append(pair[0])
#Create Alignment objects from any endID that does not start another pair (i.e. final ID in sequence)
alignments = [Alignment(end) for end in endIDs if not end in startIDs]
#Build build sequences in each original Alignment
i = len(alignments)
while i:
buildAlignments(alignments[i-1], alignments, endIDs)
i -= 1
編集: 提供された ID は、このアルゴリズムのテストに使用した小さなサンプルにすぎないことを指摘しておく必要があります。実際には、ID のシーケンスは数千に及ぶ可能性があり、多くの枝や枝から枝が離れています。
解決策: Andrew Cooke に感謝します。新しいメソッドは、コール スタック上ではるかに単純で簡単に見えるようです。私の目的により適したものにするために、彼のコードに若干の調整を加えました。以下に完成したソリューションを含めました。
from collections import defaultdict
def expand(line, have_successors, known):
#print line
known.append(line)
for child in have_successors[line[-1]]:
newline = line + [child]
if line in known: known.remove(line)
yield expand(newline, have_successors, known)
def trampoline(generator):
stack = [generator]
while stack:
try:
generator = stack.pop()
child = next(generator)
stack.append(generator)
stack.append(child)
except StopIteration:
pass
def main(pairs):
have_successors = defaultdict(lambda: set())
links = set()
for (start, end) in pairs:
links.add(end)
have_successors[start].add(end)
known = []
for node in set(have_successors.keys()):
if node not in links:
trampoline(expand([node], have_successors, 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")])
if line in known: known.remove(line)変更の概要: 1 つの ID で複数の文字を処理するために、行変数を文字列からリストに変更した完全なシリーズのみを保持するために、最初から最後までリストを作成するためにリンクと have_successors を交換し、expand に追加しました。
更新: したがって、最初にこれらすべてに問題があった理由は、提供された ID のリスト内の循環参照に対するものであることを発見しました。循環参照が修正されたので、どちらの方法も期待どおりに機能します。- あなたのご親切に感謝します。