सूची को शफ़ल करने पर अलग-अलग परिणाम

Question

मैं एक अपूर्ण ग्राफ को पृथक, अनकनेक्ट निकायों में विभाजित करना चाहता हूं। ग्राफ के किनारे सूची edges में हैं।

कोड किनारों के क्रम को घुमाने पर एक अलग परिणाम देता है। ऐसा क्यों है?

from random import shuffle 

edges = [('7', '9'), ('2', '8'), ('4', '10'), ('5', '9'), ('1', '2'), ('1', '6'), ('6', '10')] 
bodylist = [] 
shuffle(edges) 

for edge in edges: 
    #If at least one node of the edge is anywhere in bodylist, append the new nodes to that list. 
    try: 
     index = [i for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body][0] 
     bodylist[index].append(edge[0]) 
     bodylist[index].append(edge[1]) 
    #If not, make a new list containing the new nodes. 
    except: 
     bodylist.append([edge[0], edge[1]]) 

print([set(x) for x in bodylist]) 

अपेक्षित उत्पादन: [{'1', '2', '8', '4', '6', '10'}, {'9', '5', '7'}]

वास्तविक आउटपुट में से कुछ: [{'9', '5', '7'}, {'1', '2', '8'}, {'10', '4', '6', '1'}]

[{'9', '7', '5'}, {'6', '2', '1', '8'}, {'6', '10', '4'}]

ध्यान दें कि उम्मीद उत्पादन भी समय-समय पर बाहर आता है। (यह हमेशा ऐसा होना चाहिए)

मैं विभिन्न दृष्टिकोणों की भी सराहना करता हूं, क्योंकि यह शायद सबसे अच्छा नहीं है।

Answer 1

मान लीजिए आप तीन किनारों [(1, 2), (3, 4), (2, 3)] है। यह एक जुड़े ग्राफ का वर्णन करता है।

हालांकि, आपका कोड पहले (1, 2) के लिए जांच करेगा, तो इसे कुछ भी नहीं मिला bodylist पर जोड़ें।

फिर, यह (3, 4) के लिए देखेगा, न तो 3 या 4 खोजें ताकि इसे एक नई सूची के रूप में जोड़ें।

अंत में यह पहली सूची में (2, 3) जोड़ देगा लेकिन यह उसकी गलती को ठीक करने के लिए वापस नहीं आएगा, यह नहीं पता होगा कि (3, 4) एक ही शरीर से संबंधित है।

इसे सुलझाने के लिए है, तो आप पूरी तरह से पाश शेष किनारों के माध्यम से हर बार जब आप एक नया किनारे एक शरीर के लिए जाँच करने के लिए जोड़ सकते हैं अगर वहाँ एक कनेक्शन है:

while edges: 
    current_edge = edges.pop(0) 
    body = {current_edge[0], current_edge[1]} 
    i = 0 
    while i < len(edges): 
     if edges[i][0] in body or edges[i][1] in body: 
      body.add(edges[i][0]) 
      body.add(edges[i][1]) 
      edges.pop(i) # Edge added, no need to check it again 
      i = 0 # Restart the loop 
     else: 
      i += 1 
    bodylist.append(body) 

क्या आप देख रहे हैं ग्राफ के connected component कहा जाता है।

यदि आप कुशल एल्गोरिदम खोज रहे हैं, तो आपको this answer पर एक नज़र रखना चाहिए।

Answer 2

ऐसा इसलिए है क्योंकि आपका एल्गोरिदम गलत है। आपके एल्गोरिदम के साथ समस्या यह है कि यह उन किनारों पर निर्भर करता है जिन्हें हम निकायों की सूची बनाना शुरू करते हैं। इसे समझाने के लिए 4 किनारों के साथ ग्राफ का एक साधारण उदाहरण लें - edges = [('1','2'),('2','3'),('3','4'),('1','4')]।

पहला मामला -

>>> edges = [('1','2'),('2','3'),('3','4'),('1','4')] 
>>> bodylist = [] 
>>> for edge in edges: 
...  #If at least one node of the edge is anywhere in bodylist, append the new nodes to that list. 
...  try: 
...   index = [i for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body][0] 
...   bodylist[index].append(edge[0]) 
...   bodylist[index].append(edge[1]) 
...  #If not, make a new list containing the new nodes. 
...  except: 
...   bodylist.append([edge[0], edge[1]]) 
... 
>>> print([set(x) for x in bodylist]) 
[{'4', '1', '3', '2'}] 

आप कोने के साथ एक एकल शरीर मिलता है - 1, 2, 3, 4। क्यूं कर?

बीक्यूज के साथ शुरू हुआ (1,2) शरीर सूची में जोड़ा गया। फिर आपने (2,3) लिया, आप देखते हैं कि 2 शरीर सूची में जोड़े गए आइटम में पहले से ही है, आप इसे फिर से जोड़ते हैं और यह चलता है और सभी एक ही शरीर में जोड़े जाते हैं।

---

अब, एक अलग क्रम में edges = [('1','2'),('3','4'),('2','3'),('1','4')] पर एक ही किनारे लेते हैं। यह

>>> edges = [('1','2'),('3','4'),('2','3'),('1','4')] 
>>> bodylist = [] 
>>> .... #same logic 
>>> print([set(x) for x in bodylist]) 
[{'4', '1', '3', '2'}, {'4', '3'}] 

जैसा कि आप इस बार देख सकते हैं, आपको दो अलग-अलग निकायों (और जाहिर है कि वे गलत हैं) क्यों?

फिर से आप (1,2) से शुरू हुए, उन्होंने कहा कि शरीर के रूप में बॉडीलिस्ट में, फिर आप इसे देखकर (3,4) लेते हैं, आप देखते हैं कि किसी भी शरीर में कोई भी शिखर पहले से मौजूद नहीं है, इसलिए आपने इसे एक अलग शरीर में जोड़ा। तीसरा तत्व (2,3) लेते हुए, आप देखते हैं कि यह पहले और साथ ही दूसरे शरीर में भी है, लेकिन आपका तर्क केवल पहले शरीर को लेना और उसमें तत्व जोड़ना है। (जो गलत है), (आप देख सकते हैं, जहां आप गलत जा रहे हैं?)

---

यही कारण है कि आप अलग अलग परिणाम प्राप्त जब आप सूची शफ़ल के रूप में के लिए अपने तर्क के लिए महत्वपूर्ण है।

आपको क्या करना है, यदि आपको कई निकायों में किनारे के लिए शिखर मिलते हैं, तो आपको दोनों निकायों को एक ही शरीर में विलय करने की आवश्यकता होती है।

---

एक और सलाह, हम बजाय हम एक body के लिए sets उपयोग कर सकते हैं bodylist में सूचियों को जोड़ने की जरूरत नहीं है।

एक नमूना समाधान की तरह लग रहे हैं -

from random import shuffle 

edges = [('7', '9'), ('2', '8'), ('4', '10'), ('5', '9'), ('1', '2'), ('1', '6'), ('6', '10')] 
bodylist = [] 
shuffle(edges) 

for edge in edges: 
    bodies = [body for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body] 
    if len(bodies) > 0: 
     tempset = {edge[0],edge[1]} 
     for x in bodies: 
      tempset.update(x) 
      print('tempset :',tempset) 
      bodylist.remove(x) 
     bodylist.append(tempset) 
    else: 
     bodylist.append({edge[0],edge[1]}) 

print([set(x) for x in bodylist])