अनंत रिकर्सन का पता लगाएं?

Question

चलें मान मैं एक समारोह है कि एक सरणी से अधिक क्रॉल करता है ...

flatten([a, b, c, d, [e, f, g, [h, i, j, k], l], m, n, o, p]) 
>> [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p] 

समतल कोड पर और प्रत्येक सरणी का सामना करना पड़ा रिकर्सिवली कि सरणी में प्रवेश करने और वापस जाने के मूल्यों में इस तरह आप एक फ्लैट है कि होगा के लिए क्रॉल करेगा सरणी।

यह काम करता है जब तक हम इस तरह के रूप में एक सरणी है:

a = []; 
a[0] = a; 

यह स्पष्ट रूप से अनंत प्रत्यावर्तन बनाता है:

Array[1] 
0: Array[1] 
0: Array[1] 
    0: Array[1] 
    0: Array[1] 
    0: Array[1] 
    0: Array[1] 
     ... 

मैं सरणी ऐसी है कि समारोह सौदा कर सकते हैं modifiying बिना इस व्यवहार कैसे पता लगा सकते हैं इसके साथ?

Answer 1

आपको flatten() फ़ंक्शन के भीतर सरणी का एक सरणी देखना होगा और इसमें शामिल होने से पहले वहां मौजूद होने के लिए उनके अस्तित्व की जांच करनी होगी। आपको recurse पर दूसरे पैरामीटर के रूप में विज़िट किए गए तत्वों की सूची पास करनी होगी।

function recurse(ar, visited) { 
    visited = visited || []; 

    function isVisited(obj) { 
     for (var i=0;i<visited.length;i++) { 
      if (visited[i] == obj) { 
       return true; 
      } 
     } 

     visted.push(obj); // but we've visited it now 
     return false; 
    } 

    // blah blah blah, do your thing... check isVisted[i] 
} 

यदि आपका सरणी गहरा है की जाँच करने के महंगा हो जाएगा, तो आप को धोखा देने और प्रत्येक सरणी आप यात्रा पर एक विशेषता सेट कर सकते हैं, और इसके लिए जाँच (लेकिन तब जाहिर है, आप सरणी संशोधित कर रहे हैं (लेकिन नाटकीय रूप से नहीं))।

function recurse(ar) { 
    function isVisited(obj) { 
     var key = 'visited'; 
     var visited = obj.hasOwnProperty(key); 

     obj[key] = true; // but we've visited it now 

     return visited; 
    } 

    // blah blah blah, do your thing... check isVisted[i] 
} 

Answer 2

हैं का पता लगाने के प्रत्यावर्तन एक आवश्यकता है, आप इसके लिए स्मृति अंतरिक्ष व्यापार करने के लिए करने जा रहे हैं: वस्तुओं आप पार्स (पैरामीटर आप रिकर्सिवली भेजने) की एक सरणी बना सकते हैं और इसके खिलाफ प्रत्येक नए पैरामीटर की जाँच करें। यदि आपने पहले ही इसे पार्स किया है, तो तुरंत लौटें।

Answer 3

पहले से देखे गए सरणी को ट्रैक करने का एक सुविधाजनक तरीका प्रत्येक को एक "फ्लैट" संपत्ति जोड़ना होगा, शायद इसे प्रत्येक ऑपरेशन के लिए कुछ अद्वितीय मूल्य पर सेट करना होगा। अलग-अलग मानचित्र के साथ कोई बिंदु गड़बड़ नहीं होता है जब प्रत्येक सरणी पहले से ही पूरी तरह से अच्छी वस्तु है।

Answer 4

असली दुनिया में, चरण 1 आपको अपमानजनक देवता ढूंढना है जिसने आपको स्वयं-संदर्भ वस्तु सौंपी और उन्हें छड़ी से मारा।

समस्या हल हो जाती है, हालांकि, उन्हें जगह में आत्म-संदर्भ के रूप में समाप्त कर दिया जाता है। उन्हें प्रतियों में बदल दें। Array.slice मूल को बदलने के बिना सरणी के हिस्सों (पूर्ण प्रतियों सहित) देता है।

if(thisElement.constructor.prototype.slice){ //is it an array 
    thisElement = thisElement.slice(0); //now it's a new but identical array 
} 

ध्यान दें कि यह केवल मुख्य सरणी संदर्भ पर ही है। आंतरिक सरणी संदर्भों को अभी भी बदलने की आवश्यकता होगी क्योंकि प्रतिलिपि संदर्भ अभी भी एक ही चीज़ पर इंगित करता है।

इसके अलावा, यदि आप उन पात्रों के बारे में धारणाएं बना सकते हैं जो निश्चित रूप से मौजूद नहीं होंगे, तो आप स्लाइस/बहुत उपयोगी होने के लिए शामिल हो सकते हैं। ,

var is_recursive = false; 

try { 
    JSON.stringify(my_recursive_object); 
} catch (e) { 
    if (e.name = 'TypeError') 
     is_recursive = true; 
    else 
     throw e; 
} 

मैं इस सवाल का एक बेहतर जवाब की तलाश में मिला हालांकि - हालांकि यह कोई चाहने मदद कर सकता है:

Answer 5

एक अन्य, अधिक गंदा तरीका है (लेकिन कम से कम उपद्रव के लिए अच्छा) सिर्फ JSON encoder का उपयोग करने के लिए है एक अच्छा हैक ;-)