मैं कैसे निर्धारित कर सकता हूं कि एक कंटेनर असीम रूप से रिकर्सिव है और इसका सबसे छोटा अद्वितीय कंटेनर ढूंढता है?

Question

मैं Flatten (an irregular) list of lists पढ़ रहा था और इसे पायथन अभ्यास के रूप में अपनाने का फैसला किया - एक छोटा सा फ़ंक्शन जिसे मैं कभी-कभी अभ्यास के लिए, मूल का जिक्र किए बिना फिर से लिखूंगा। पहली बार मैं इस कोशिश की, मैं निम्नलिखित की तरह कुछ था:

def flat(iterable): 
    try: 
     iter(iterable) 
    except TypeError: 
     yield iterable 
    else: 
     for item in iterable: 
      yield from flatten(item) 

यह नेस्ट list संख्या से युक्त रों जैसी बुनियादी संरचनाओं के लिए ठीक काम करता है, लेकिन तार यह दुर्घटना क्योंकि श्रृंखला का पहला तत्व एक एकल चरित्र है स्ट्रिंग, जिसका पहला तत्व स्वयं है, जिसका पहला तत्व स्वयं ही है, और इसी तरह। उपरोक्त लिंक को जांचते हुए, मुझे एहसास हुआ कि स्ट्रिंग के लिए चेक बताता है।

def flatter(iterable): 
    try: 
     iter(iterable) 
     if isinstance(iterable, str): 
      raise TypeError 
    except TypeError: 
     yield iterable 
    else: 
     for item in iterable: 
      yield from flatten(item) 

अब यह रूप में अच्छी तरह तार के लिए काम करता है: जो मुझे निम्नलिखित दे दी है। हालांकि, मैंने तब याद किया कि list में स्वयं के संदर्भ हो सकते हैं।

>>> lst = [] 
>>> lst.append(lst) 
>>> lst 
[[...]] 
>>> lst[0][0][0][0] is lst 
True 

तो, एक स्ट्रिंग केवल प्रकार है कि समस्या की इस तरह का कारण बन सकता है। इस बिंदु पर, मैंने स्पष्ट समस्या-जांच के बिना इस मुद्दे के खिलाफ सुरक्षा के लिए एक रास्ता तलाशना शुरू कर दिया।

निम्नलिखित flattener.py ensued। flattish() एक ऐसा संस्करण है जो केवल तारों के लिए जांच करता है। flatten_notype() जांच करता है कि किसी वस्तु का पहला आइटम का पहला आइटम रिकर्सन निर्धारित करने के लिए स्वयं के बराबर है या नहीं। flatten() यह करता है और फिर जांच करता है कि ऑब्जेक्ट या उसके पहले आइटम का पहला आइटम दूसरे प्रकार का उदाहरण है या नहीं। Fake कक्षा मूल रूप से अनुक्रमों के लिए एक रैपर को परिभाषित करती है। प्रत्येक फ़ंक्शन का परीक्षण करने वाली रेखाओं पर टिप्पणियां should be `desired_result` [> `undesired_actual_result`] रूप में परिणामों का वर्णन करती हैं। जैसा कि आप देख सकते हैं, प्रत्येक एक स्ट्रिंग के चारों ओर लिपटा Fake पर विभिन्न तरीकों से विफल रहता है, Fake पूर्णांकों, एकल चरित्र तार, और बहु-चरित्र स्ट्रिंग की एक list के चारों ओर लिपटा।

>>> print(*flatten(lst)) 
[[...]] 
>>> lst.append(0) 
>>> print(*flatten(lst)) 
[[...], 0] 
>>> print(*list(flatten(lst))[0]) 
[[...], 0] 0 

आप देख सकते हैं, यह इसी तरह 1 ('a',) bc करने के साथ ही अपने स्वयं के विशेष तरीके से के रूप में विफल रहता है:

def flattish(*i): 
    for item in i: 
     try: iter(item) 
     except: yield item 
     else: 
      if isinstance(item, str): yield item 
      else: yield from flattish(*item) 

class Fake: 
    def __init__(self, l): 
     self.l = l 
     self.index = 0 
    def __iter__(self): 
     return self 
    def __next__(self): 
     if self.index >= len(self.l): 
      raise StopIteration 
     else: 
      self.index +=1 
      return self.l[self.index-1] 
    def __str__(self): 
     return str(self.l) 

def flatten_notype(*i): 
    for item in i: 
     try: 
      n = next(iter(item)) 
      try: 
       n2 = next(iter(n)) 
       recur = n == n2 
      except TypeError: 
       yield from flatten(*item) 
      else: 
       if recur: 
        yield item 
       else: 
        yield from flatten(*item) 
     except TypeError: 
      yield item 

def flatten(*i): 
    for item in i: 
     try: 
      n = next(iter(item)) 
      try: 
       n2 = next(iter(n)) 
       recur = n == n2 
      except TypeError: 
       yield from flatten(*item) 
      else: 
       if recur: 
        yield item if isinstance(n2, type(item)) or isinstance(item, type(n2)) else n2 
       else: 
        yield from flatten(*item) 
     except TypeError: 
      yield item 


f = Fake('abc') 

print(*flattish(f)) # should be `abc` 
print(*flattish((f,))) # should be `abc` > `` 
print(*flattish(1, ('a',), ('bc',))) # should be `1 a bc` 

f = Fake([1, 2, 3]) 

print(*flattish(f)) # should be `1 2 3` 
print(*flattish((f,))) # should be `1 2 3` > `` 
print(*flattish(1, ('a',), ('bc',))) # should be `1 a bc` 

f = Fake('abc') 
print(*flatten_notype(f)) # should be `abc` 
print(*flatten_notype((f,))) # should be `abc` > `c` 
print(*flatten_notype(1, ('a',), ('bc',))) # should be `1 a bc` > `1 ('a',) bc` 

f = Fake([1, 2, 3])  

print(*flatten_notype(f)) # should be `1 2 3` > `2 3` 
print(*flatten_notype((f,))) # should be `1 2 3` > `` 
print(*flatten_notype(1, ('a',), ('bc',))) # should be `1 a bc` > `1 ('a',) bc` 

f = Fake('abc') 
print(*flatten(f)) # should be `abc` > `a` 
print(*flatten((f,))) # should be `abc` > `c` 
print(*flatten(1, ('a',), ('bc',))) # should be `1 a bc` 

f = Fake([1, 2, 3])  

print(*flatten(f)) # should be `1 2 3` > `2 3` 
print(*flatten((f,))) # should be `1 2 3` > `` 
print(*flatten(1, ('a',), ('bc',))) # should be `1 a bc` 

मैं भी पुनरावर्ती lst ऊपर परिभाषित और flatten() साथ निम्नलिखित की कोशिश की है।

मैं how can python function access its own attributes? पढ़ सोच के हर वस्तु यह देखा था कि शायद समारोह ट्रैक रखने के सकता है, लेकिन वह काम नहीं होगा क्योंकि या तो हमारे lst पहचान और समानता मिलान के साथ एक वस्तु है, तार वस्तुओं है कि केवल मिलान समानता हो सकती है शामिल , और flatten([1, 2], [1, 2]) जैसे कुछ की संभावना के कारण समानता पर्याप्त नहीं है।

क्या कोई विश्वसनीय तरीका है (यानी ज्ञात प्रकारों की जांच नहीं करता है, यह आवश्यक नहीं है कि एक कंटेनर कंटेनर और उसके कंटेनर सभी एक ही प्रकार के हों, आदि) यह जांचने के लिए कि एक कंटेनर संभावित क्षमता वाले वस्तुओं को रखता है या नहीं अनंत रिकर्सन, और विश्वसनीय रूप से सबसे छोटा अद्वितीय कंटेनर निर्धारित करते हैं? यदि ऐसा है, तो कृपया समझाएं कि यह कैसे किया जा सकता है, यह विश्वसनीय क्यों है, और यह विभिन्न पुनरावर्ती परिस्थितियों को कैसे संभालता है। यदि नहीं, तो कृपया समझाएं कि यह तर्कसंगत क्यों असंभव है।

Answer 1

मैं वहाँ पता लगाने के लिए अगर एक मनमाना iterable अनंत है एक विश्वसनीय तरीका है नहीं लगता।सबसे अच्छा हम कर सकते हैं ढेर थकाऊ बिना इस तरह के एक iterable से असीम पुरातन उपज के लिए, उदाहरण के लिए है:

from collections import deque 

def flat(iterable): 

    d = deque([iterable]) 

    def _primitive(x): 
     return type(x) in (int, float, bool, str, unicode) 

    def _next(): 
     x = d.popleft() 
     if _primitive(x): 
      return True, x 
     d.extend(x) 
     return False, None 

    while d: 
     ok, x = _next() 
     if ok: 
      yield x 


xs = [1,[2], 'abc'] 
xs.insert(0, xs) 

for p in flat(xs): 
    print p 

की "आदिम" उपरोक्त परिभाषा है, ठीक है, आदिम, लेकिन यह निश्चित रूप से सुधार किया जा सकता।

Answer 2

कुछ इस तरह के बारे में क्या:

def flat(obj, used=[], old=None):   
    #This is to get inf. recurrences 
    if obj==old: 
     if obj not in used: 
      used.append(obj) 
      yield obj 
     raise StopIteration 
    try: 
     #Get strings 
     if isinstance(obj, str): 
      raise TypeError 
     #Try to iterate the obj 
     for item in obj: 
      yield from flat(item, used, obj) 
    except TypeError: 
     #Get non-iterable items 
     if obj not in used: 
      used.append(obj) 
      yield obj 

(प्रत्यावर्तन) की एक सीमित संख्या के बाद कदम एक सूची iterable तत्व के रूप में खुद को ज्यादा से ज्यादा शामिल होंगे (जब से हम परिमित कई चरणों में उत्पन्न करने के लिए है)। के तत्व में के साथ हम obj==old के साथ परीक्षण करते हैं।

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

परीक्षण यह कुछ सूचियों के साथ काम करने के लिए लगता है:

>> lst = [1] 
>> lst.append(lst) 
>> print('\nList1: ', lst)  
>> print([x for x in flat(lst)]) 
List1:  [1, [...]] 
Elements: [1, [1, [...]]] 

#We'd need to reset the iterator here! 
>> lst2 = [] 
>> lst2.append(lst2) 
>> lst2.append((1,'ab')) 
>> lst2.append(lst) 
>> lst2.append(3) 
>> print('\nList2: ', lst2)  
>> print([x for x in flat(lst2)]) 
List2:  [[...], (1, 'ab'), [1, [...]], 3] 
Elements: [[[...], (1, 'ab'), [1, [...]], 3], 1, 'ab', [1, [...]], 3] 

नोट: यह वास्तव में समझ में आता है कि अनंत सूचियों [[...], (1, 'ab'), [1, [...]], 3] और [1, [...]] तत्वों के रूप में माना जाता है क्योंकि इन्हें वास्तव में स्वयं शामिल किया जाता है लेकिन यदि यह वांछित नहीं है तो ऊपर दिए गए कोड में पहले yield पर टिप्पणी कर सकते हैं।

Answer 3

आपके टेस्ट कोड के साथ कोई समस्या है जो रिकर्सिव कंटेनर समस्या से संबंधित नहीं है जिसे आप हल करने का प्रयास कर रहे हैं। मुद्दा यह है कि आपकी Fake कक्षा एक पुनरावर्तक है और केवल एक बार उपयोग की जा सकती है। अपने सभी मूल्यों को फिर से शुरू करने के बाद, यह हमेशा StopIteration बढ़ाएगा जब आप इसे फिर से चालू करने का प्रयास करेंगे।

तो अगर आप एक ही Fake उदाहरण पर एक से अधिक कार्य कर, आप कुछ भी खाली उत्पादन हो के बाद पहला ऑपरेशन iterator उपयोग किए गए प्राप्त करने की उम्मीद नहीं करनी चाहिए। यदि आप प्रत्येक ऑपरेशन से पहले इटरेटर को फिर से बनाते हैं, तो आपको वह समस्या नहीं होगी (और आप वास्तव में रिकर्सन समस्या को हल करने का प्रयास कर सकते हैं)।

तो इस मुद्दे पर। अनंत रिकर्सन से बचने का एक तरीका उन वस्तुओं के साथ एक ढेर को बनाए रखना है जिन्हें आप वर्तमान में घोंसला में रखते हैं। यदि आप जो अगला मूल्य देखते हैं वह पहले से ही ढेर पर है, तो आप जानते हैं कि यह रिकर्सिव है और इसे छोड़ सकता है। यहाँ ढेर के रूप में एक सूची का उपयोग कर इस का एक कार्यान्वयन है:

def flatten(obj, stack=None): 
    if stack is None: 
     stack = [] 

    if obj in stack: 
     yield obj 

    try: 
     it = iter(obj) 
    except TypeError: 
     yield obj 
    else: 
     stack.append(obj) 
     for item in it: 
      yield from flatten(item, stack) 
     stack.pop() 

ध्यान दें कि यह अभी भी एक ही कंटेनर एक बार से अधिक से मूल्यों को प्राप्त हो सकते हैं, जब तक यह नहीं लगाए गए है के भीतर ही (x=[1, 2]; y=[x, 3, x]; print(*flatten(y)) के लिए जैसे 1 2 3 1 2 प्रिंट होगा) ।

यह भी तार में recurse करता है, लेकिन यह केवल केवल एक ही स्तर के लिए ऐसा करेंगे, तो flatten("foo") पत्र 'f', 'o' और 'o' बदले में निकलेगा। यदि आप इससे बचना चाहते हैं, तो संभवतः फ़ंक्शन को जागरूक करने की आवश्यकता है, क्योंकि पुनरावृत्ति प्रोटोकॉल के परिप्रेक्ष्य से, एक स्ट्रिंग अपने अक्षरों के एक पुनरावर्तक कंटेनर से अलग नहीं है। यह केवल एक ही चरित्र तार है जो खुद को शामिल करता है।

Answer 4

आपके द्वारा पूछे जाने वाले परिदृश्य को बहुत कम परिभाषित किया गया है। जैसा कि आपके प्रश्न में परिभाषित किया गया है, यह जांचना असंभव है कि एक कंटेनर संभावित अनंत रिकर्सन के साथ पुनरावृत्त वस्तुओं को रखता है [।] "आपके प्रश्न के दायरे पर एकमात्र सीमा" पुन: प्रयोज्य "वस्तु है।आधिकारिक अजगर प्रलेखन को परिभाषित करता है "iterable" इस प्रकार है:

एक एक समय में अपने सदस्यों को वापस लौटाते में सक्षम आपत्ति है। पुनरावृत्तियों के उदाहरणों में सभी अनुक्रम प्रकार (जैसे सूची, str, और tuple) और कुछ गैर-अनुक्रम प्रकार जैसे कि dict, फ़ाइल ऑब्जेक्ट्स और किसी भी कक्षा के ऑब्जेक्ट्स शामिल हैं जिन्हें आप __iter__() या __getitem__() विधि से परिभाषित करते हैं। [...]

यहाँ कुंजी वाक्यांश है "किसी भी कक्षा एक __iter__() या __getitem__() विधि के साथ [परिभाषित]।" यह मांग पर उत्पन्न सदस्यों के साथ "पुन: प्रयोज्य" वस्तुओं की अनुमति देता है। उदाहरण के लिए, मान लीजिए कि कोई स्ट्रिंग ऑब्जेक्ट्स का एक समूह उपयोग करना चाहता है जो उस समय के आधार पर क्रोनोलॉजिकल ऑर्डर में सॉर्ट और तुलना करता है जिस पर विशेष स्ट्रिंग बनाई गई थी। वे या तो अपनी कार्यक्षमता को दोबारा विभाजित करते हैं या प्रत्येक कार्यक्षमता को timestampedString() ऑब्जेक्ट से जुड़े टाइमस्टैम्प जोड़ते हैं, और तदनुसार तुलना विधियों को समायोजित करते हैं।

सूचकांक स्थान के आधार पर सबस्ट्रिंग तक पहुंचना एक नया स्ट्रिंग बनाने का एक तरीका है, इसलिए len() == 1 के timestampedString() वैध तरीके से जब आप का उपयोग timestampedString()[0:1] एक ही चरित्र लेकिन एक नए टाइमस्टैम्प के साथ len() == 1 के timestampedString() लौट सकते हैं। चूंकि टाइमस्टैम्प विशिष्ट ऑब्जेक्ट इंस्टेंस का हिस्सा है, वहां कोई भी प्रकार का पहचान परीक्षण नहीं है जो कहता है कि दो ऑब्जेक्ट समान हैं जब तक कि एक ही वर्ण वाले किसी भी दो स्ट्रिंग को समान नहीं माना जाता है। आप अपने प्रश्न में बताते हैं कि यह मामला नहीं होना चाहिए।

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

हालांकि, एल्गोरिदमिक रूप से बाध्यता को लागू करना कि कंटेनर में केवल स्थिर वस्तुएं होती हैं, एक और समस्या प्रस्तुत करती है: इसे कुछ पूर्व-अनुमोदित सूची जैसे प्राइमेटिव्स की कुछ धारणा के खिलाफ टाइप-जांच की आवश्यकता होती है। वस्तुओं की दो श्रेणियों को तब समायोजित किया जा सकता है: एक ज्ञात-स्थिर प्रकार (जैसे प्राइमेटिव) और कंटेनर की एकल वस्तुएं जिसके लिए निहित वस्तुओं की संख्या अग्रिम में निर्धारित की जा सकती है। बाद की श्रेणी को तब सीमित किया जा सकता है जब कई निहित वस्तुओं को फिर से चालू किया गया है और सभी को सीमित माना गया है। कंटेनर के भीतर कंटेनर को पुनरावर्ती तरीके से संभाला जा सकता है। ज्ञात-स्थैतिक प्रकार एकल वस्तुएं रिकर्सिव बेस-केस हैं।

यदि कंटेनर अधिक ऑब्जेक्ट्स उत्पन्न करता है, तो यह इस श्रेणी की वस्तु की परिभाषा का उल्लंघन करता है। पायथन में मनमानी वस्तुओं को अनुमति देने में समस्या यह है कि इन वस्तुओं को पायथन कोड में परिभाषित किया जा सकता है जो सी कोड में लिखे गए घटकों का उपयोग कर सकते हैं और किसी भी अन्य भाषा को सी से जोड़ा जा सकता है। यह निर्धारित करने के लिए इस कोड का मूल्यांकन करने का कोई तरीका नहीं है कि यह वास्तव में स्थिर आवश्यकता का अनुपालन करता है या नहीं।

Answer 5

आवर्ती कंटेनर फ़्लैटनिंग से बचें। नीचे दिए गए उदाहरण में keepobj उनका ट्रैक रखता है और keepcls किसी निश्चित प्रकार के कंटेनर को अनदेखा करता है। मेरा मानना ​​है कि यह 2.3 के लिए काम करता है।

def flatten(item, keepcls=(), keepobj=()): 
    if not hasattr(item, '__iter__') or isinstance(item, keepcls) or item in keepobj: 
     yield item 
    else: 
     for i in item: 
      for j in flatten(i, keepcls, keepobj + (item,)): 
       yield j 

यह lst = [1, 2, [5, 6, {'a': 1, 'b': 2}, 7, 'string'], [...]] तरह परिपत्र सूचियों समतल और तार और dicts अन-चपटा जैसे कुछ कंटेनर रख सकते हैं।

>>> list(flatten(l, keepcls=(dict, str))) 
[1, 2, 5, 6, {'a': 1, 'b': 2}, 7, 'string', [1, 2, [5, 6, {'a': 1, 'b': 2}, 7, 'string'], [...]]] 

यह भी निम्नलिखित मामले से काम करता है:

>>> list(flatten([[1,2],[1,[1,2]],[1,2]])) 
[1, 2, 1, 1, 2, 1, 2] 

आप समारोह अधिक संक्षिप्त बुला बनाने के लिए keepcls में कुछ डिफ़ॉल्ट कक्षाओं रखने के लिए चाहते हो सकता है।