जांचें कि मैट्रिक्स में कुछ तत्व एकजुट हैं

Question

मुझे एक बहुत ही छोटा पायथन प्रोग्राम लिखना है जो जांचता है कि निर्देशांक के कुछ समूह सभी एक साथ जुड़े हुए हैं (रेखा से, तिरछे नहीं)। अगले 2 चित्र दिखाते हैं कि मेरा क्या मतलब है। छोड़ दिया चित्र में सभी रंगीन समूहों सही तस्वीर नहीं है, एकजुट कर रहे हैं:

मैं पहले से ही कोड के इस टुकड़े कर दिया है, लेकिन यह काम करने के लिए प्रतीत नहीं होता है और मैं काफी अटक कर रहा हूँ, कोई राय कि इसे कैसे ठीक किया जाए?

def cohesive(container): 
    co = container.pop() 
    container.add(co) 
    return connected(co, container) 

def connected(co, container): 
    done = {co} 
    todo = set(container) 
    while len(neighbours(co, container, done)) > 0 and len(todo) > 0: 
     done = done.union(neighbours(co, container, done)) 
    return len(done) == len(container) 

def neighbours(co, container, done): 
    output = set() 
    for i in range(-1, 2): 
     if i != 0: 
      if (co[0] + i, co[1]) in container and (co[0] + i, co[1]) not in done: 
       output.add((co[0] + i, co[1])) 
      if (co[0], co[1] + i) in container and (co[0], co[1] + i) not in done: 
       output.add((co[0], co[1] + i)) 
    return output 

इस

कुछ संदर्भ सामग्री है कि True लौट जाना है:

cohesive({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)}) 

और इस False लौटना चाहिए:

cohesive({(1, 2), (1, 4), (2, 2), (0, 3), (0, 4)}) 

दोनों परीक्षण काम करते हैं, लेकिन जब मैं अलग से यह परीक्षण करने की कोशिश संख्याओं की संख्या विफल हो जाती है।

Answer 1

आप केवल एक तत्व ले सकते हैं और संभव होने पर अपने पड़ोसियों को संलग्न कर सकते हैं।

def dist(A,B):return abs(A[0]-B[0]) + abs(A[1]-B[1]) 

def grow(K,E):return {M for M in E for N in K if dist(M,N)<=1} 

def cohesive(E): 
    K={min(E)} # an element 
    L=grow(K,E) 
    while len(K)<len(L) : K,L=L,grow(L,E) 
    return len(L)==len(E) 

grow(K,E) वापसी K के पड़ोस।

In [1]: cohesive({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)}) 
Out[1]: True 

In [2]: cohesive({(1, 2), (1, 4), (2, 2), (0, 3), (0, 4)}) 
Out[2]: False 

Answer 2

आमतौर पर, यह जांचने के लिए कि क्या कुछ जुड़ा हुआ है, आपको अलग सेट डेटा संरचनाओं का उपयोग करने की आवश्यकता है, अधिक कुशल भिन्नताओं में भारित त्वरित संघ, पथ संपीड़न के साथ भारित त्वरित संघ शामिल हैं।

यहां एक कार्यान्वयन है, http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html जिसे आप अपनी आवश्यकताओं में संशोधित कर सकते हैं। साथ ही, ए अहो द्वारा "द डिज़ाइन एंड एनालिसिस ऑफ कंप्यूटर एल्गोरिदम" पुस्तक में पाया गया कार्यान्वयन, आपको उस समूह का नाम निर्दिष्ट करने की अनुमति देता है जिसमें आप 2 कनेक्टेड तत्व जोड़ते हैं, इसलिए मुझे लगता है कि वह संशोधन है जिसे आप ढूंढ रहे हैं (इसमें केवल 1 अतिरिक्त सरणी का उपयोग करना शामिल है जो समूह संख्याओं का ट्रैक रखता है)।

एक साइड नोट के रूप में, क्योंकि अलग-अलग सेट आम तौर पर सरणी पर लागू होते हैं, यह न भूलें कि आप एन मैट्रिक्स द्वारा आकार एन * एन की सरणी के रूप में एन का प्रतिनिधित्व कर सकते हैं।

संपादित करें: सिर्फ महसूस किया कि यह मेरे लिए स्पष्ट है कि तुम क्या पहली बार में पूछ रहे थे नहीं था, और मैंने महसूस किया कि आप यह भी कहा कि कि विकर्ण घटकों, जुड़े नहीं हैं कि इस मामले में एल्गोरिथ्म इस प्रकार है:

0) जांचें कि सभी तत्व एक ही समूह को संदर्भित करते हैं या नहीं।

1) प्रश्नों में मैट्रिक्स में निर्देशांक का प्रतिनिधित्व करने वाले जोड़े की सरणी के माध्यम से Iterate।

|entry.x - otherEntry.x| + |entry.y - otherEntry.y|=1. 

'प्रविष्टि' तत्व यह है कि पाश के लिए बाहरी करने के लिए बात कर रहा है को संदर्भित करता है:

2) प्रत्येक जोड़ी के लिए जोड़ों का एक समूह है कि निम्न सूत्र को संतुष्ट कर सकते हैं।

3) जांचें कि सभी सेट ओवरलैप हैं या नहीं। यदि आप 1 से अधिक सेट प्राप्त करते हैं, तो अंत में सेट को "संघनित" करके किया जा सकता है, तो तत्व एकजुट नहीं होते हैं।

जटिलता ओ (एन^2 + एन^2 * लॉग (एन)) है।

उदाहरण:

(0,4), (1,2), (1,4), (2,2), (2,3)

0) की जाँच है कि वे सभी कर रहे हैं एक ही समूह में:

SET1: (0,4), (1,4)

उन सभी को बनाने के सेट समूह 5.

1) के हैंसेट 2: (1,2), (2,2)

सेट 3: (0,4), (1,4) // यहां हम मानते हैं कि सेट सॉर्ट किए गए हैं, इसके अलावा होना चाहिए (1 , 4), (0,4)

SET4: (1,2), (2,2), (2,3)

set5: (2,2), (2,3)

2) ओवरलैप के लिए जाँच:

SET1 set3 के साथ ओवरलैप हो, तो हम पाते हैं:

SET1 ' : (0,4), (1,4)

SET2 SET4 के साथ ओवरलैप हो और 5 निर्धारित करते हैं, तो हम पाते हैं:

SET2 ': (1,2), (2,2), (2, 3)

जैसा कि आप सेट 1 और सेट 2 'ओवरलैप नहीं देख सकते हैं, इसलिए आपको एक ही समूह में 2 अलग-अलग सेट मिलते हैं, इसलिए उत्तर' झूठा 'है।

ध्यान दें कि यह अक्षम है, लेकिन मुझे नहीं पता कि इसे और अधिक कुशलता से कैसे किया जाए, लेकिन यह आपके प्रश्न का उत्तर देता है।

Answer 3

आपके जुड़े हुए फ़ंक्शन में तर्क गलत लगता है। आप एक टोडो चर बनाते हैं, लेकिन फिर कभी भी इसकी सामग्री नहीं बदलते हैं। आप हमेशा एक ही शुरुआती बिंदु के आसपास पड़ोसियों की तलाश करते हैं।

बजाय इस कोड का प्रयास करें:

def connected(co, container): 
    done = {co} 
    todo = {co} 
    while len(todo) > 0: 
     co = todo.pop() 
     n = neighbours(co, container, done) 
     done = done.union(n) 
     todo = todo.union(n) 
    return len(done) == len(container) 

todo सभी बिंदुओं हम अभी भी कर रहे हैं की जाँच करने के का एक सेट है।

done उन सभी बिंदुओं का एक सेट है जो हमें शुरुआती बिंदु से 4-जुड़े हुए हैं।

Answer 4

मैं इस समस्या को अलग ढंग से निपटने हूँ ... आप पांच वास्तव में के लिए देख रहे हैं, इसका मतलब है कि:

1. हर पंक्ति में समन्वय एक और लाइन में समन्वय पड़ोसी हो गया है, क्योंकि कुछ भी कम इसका मतलब है कि समन्वय डिस्कनेक्ट है।
2. कम से कम तीन निर्देशांकों को लाइन में दो या दो से अधिक समन्वय पड़ोस करना पड़ता है, क्योंकि कुछ भी कम और समूह डिस्कनेक्ट हो जाएंगे।

इसलिए, आप समन्वयक के पड़ोसियों को प्राप्त कर सकते हैं और जांच सकते हैं कि दोनों स्थितियां पूरी हो चुकी हैं या नहीं।

यहाँ एक बुनियादी समाधान है:

def cells_are_connected(connections): 
    return all(c > 0 for c in connections) 

def groups_are_connected(connections): 
    return len([1 for c in connections if c > 1]) > 2 

def cohesive(coordinates): 
    connections = [] 
    for x, y in coordinates: 
     neighbours = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] 
     connections.append(len([1 for n in neighbours if n in coordinates])) 
    return cells_are_connected(connections) and groups_are_connected(connections) 

print cohesive([(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)]) # True 
print cohesive([(1, 2), (1, 4), (2, 2), (0, 3), (0, 4)]) # False 

एक सामान्य मामला समाधान या संघ तर्क के लिए कोई ज़रूरत नहीं। :) ध्यान दें कि यह पांच-इन-लाइन-लाइन समस्या के लिए विशिष्ट है, हालांकि।