मैंने एक ऐसा फ़ंक्शन बनाया है जो आईडी जोड़े की सूचियों को पढ़ता है (यानी [("ए", "बी"), ("बी", "सी"), ("सी", "डी "), ...] और किसी भी शाखाओं सहित आईडी को शुरू करने से अनुक्रमित करता है।पायथन रिकर्सिव फ़ंक्शन रिकर्सन सीमा से अधिक है। मैं इसे पुनरावृत्ति में कैसे बदल सकता हूं
आदेशित आईडी की प्रत्येक सूची एक संरेखण नामक कक्षा में आयोजित की जाती है और यह फ़ंक्शन एक नया संरेखण शुरू करके शाखाओं को संभालने के लिए रिकर्सन का उपयोग करता है आईडी पर जिस पर शाखा मुख्य सूची से विभाजित होती है।
मुझे पता चला है कि कुछ इनपुट के साथ पायथन द्वारा निर्धारित अधिकतम रिकर्सन सीमा तक पहुंचना संभव है। मुझे पता है कि मैं 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
संपादित करें: मैं कहना चाहिए कि प्रदान की आईडी सिर्फ एक छोटा सा नमूना मैं इस एल्गोरिथ्म के परीक्षण के लिए इस्तेमाल किया जा सकता है। वास्तविकता में, आईडी की अनुक्रम शाखाओं से कई शाखाओं और शाखाओं के साथ कई हजार लंबी हो सकती है।
समाधान: एंड्रयू कुक के लिए धन्यवाद। नई विधि कॉल स्टैक पर बहुत आसान और बहुत आसान लगती है। मैंने अपने उद्देश्यों के अनुरूप बेहतर तरीके से अपने कोड में कुछ मामूली समायोजन किए हैं। शुरू से ही सूची जोड़ा if line in known: known.remove(line) क्रम में ही पूरी श्रृंखला बदली हुई लाइन स्ट्रिंग से चर बनाए रखने के लिए विस्तार करने के लिए समाप्त करने के लिए बनाने के लिए बदली लिंक और have_successors: परिवर्तन की
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")])
सारांश: मैं नीचे पूरा समाधान को शामिल किया है एक आईडी में एकाधिक वर्णों को संभालने के लिए सूची में।
अद्यतन: तो मैंने अभी पाया है कि मुझे यह सब कुछ पता था क्योंकि मुझे यह उपलब्ध कराई गई आईडी की सूची में परिपत्र संदर्भों के लिए किया गया है। अब जब परिपत्र संदर्भ तय किया गया है, तो विधि अपेक्षा के अनुसार काम करता है। - आपके सहयोग के लिए पुन: धन्यवाद।
मुझे लगता है कि आपका मतलब ऑफशूट है। –
क्या यह आपका वास्तविक कोड है? यह इंडेक्स एरर को 'i = len (alignments)' पर फेंकता है ... 'बिल्ड एलाइनमेंट्स (संरेखण [i]' इससे पहले कि यह भी रिकर्सिंग शुरू हो जाए। –
@Erin - इसे इंगित करने के लिए धन्यवाद। मैंने ऑफ-च्यूट्स को शाखाओं में बदल दिया है एक बेहतर विवरण। – Brian