समूह समान आंकड़ों के एल्गोरिथ्म की तलाश में

Question

एक साधारण सवाल है, लेकिन एक जवाब है कि कर दिया गया है मुझे दिनों के लिए परेशान ...

2 उपनाम के इनपुट एक सरणी (php) के रूप में है, मान लें:

Array(
    Array(1,5), 
    Array(6,8), 
    Array(6,1), 
    Array(9,3), 
) 

उन राज्य के प्रत्येक "1" के रूप में "5" एक ही है, "6" के रूप में "8" एक ही है, ... सरल, अब मैं समूह में वे की जरूरत है, ऊपर के उदाहरण को देखकर , एल्गोरिदम मुझे देना चाहिए, अगर मैं अच्छी तरह से पूछता हूं, दो समूह:

Array(1,5,6,8) and Array(9,3) 

सरल कम्यूटेशन तर्क, लेकिन मुझे कोड के साथ निपटने का कोई तरीका नहीं मिल रहा है! किसी भी दिशानिर्देश की सराहना की जाएगी !!

Answer 1

मैं इनसे कुछ प्रकार का पेड़ तैयार करूंगा, और घटकों को अलग करने के लिए रंगीनकरण का उपयोग करूंगा। उदाहरण के लिए जी = [ई, वी], ई = {1, 5, 6, 7, 9}, वी = {{1,5}, {6,8}, {6,1}, {9, 3}} जहां जी वी वर्टिस और ई किनारों वाला ग्राफ है। अब एक यादृच्छिक वर्टेक्स के साथ शुरू करें, रंगीन रूप से इसके सभी पड़ोसी रंग सी 1 (ब्रेडथ-पहली खोज के साथ) रंग से। यदि आप नए पड़ोसियों को नहीं ढूंढ पा रहे हैं तो आपको पहला समूह मिला है। अब एक नए uncolored vertex और एक नया रंग सी 2 के साथ शुरू करें। इसे तब तक दोहराएं जब तक आपके पास कोई और शिखर न हो।

Answer 2

यह एक पृथक सेट यूनियन समस्या का एक उदाहरण है।

विकिपीडिया इसके बारे में यहाँ एक पृष्ठ है:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

कुछ नमूना एल्गोरिदम कि विकिपीडिया पृष्ठ पर समस्या का समाधान कर रहे हैं। क्या विकिपीडिया आपके लिए पर्याप्त स्पष्ट है?

Answer 3

आप संघ-खोज एल्गोरिदम का उपयोग करके यह बहुत तेज़ कर सकते हैं।

विचार पेड़ों का जंगल होना है, जहां प्रत्येक पेड़ तत्वों का प्रतिनिधित्व करता है जो "बराबर हैं"। आप इस पेड़ को एक साधारण सरणी के रूप में दर्शाते हैं, जहां एक [i] या तो मैं माता-पिता का हो सकता हूं, -1 यदि मैं रूट हूं, या कहूं -2 यदि मैं अभी तक पेड़ में नहीं हूं।

आपके मामले में आप साधारण पेड़ के साथ शुरू होगा:

1 
\ 
    5 

अगली बात आप इसे 6 और 8 में शामिल होने का हालांकि चाहते हैं, वे दोनों असाइन नहीं किए गए हैं, तो आप आप एक नया पेड़ जोड़ें। (यह एक [6] = है - 1, एक [8] = 6):

1 6 
\ \ 
    5 8 

अब आप 6 और 1. आप जो सेट वे हैं यह पता लगाने में शामिल करना चाहते करने के लिए, करने के लिए अपने माता-पिता का पालन करते हुए शीर्ष। संयोग से वे दोनों जड़ें हैं। इस मामले में हम दूसरे पेड़ के बच्चे को सबसे छोटा पेड़ बनाते हैं। (क [6] = 1)

1 
/\ 
6 5 
\ 
    8 

अंत में हम 9 और 3 में शामिल करना चाहते, वे दोनों असाइन नहीं किए गए हैं, इसलिए हम एक नया पेड़ पैदा करते हैं। (एक [3] = - 1, एक [9] = 3)

1 9 
/\ \ 
6 5 3 
\ 
    8 

कहें कि आपके पास 5 = 3 भी है? जब तक आप जड़ों तक नहीं पहुंच जाते, तब तक अपने माता-पिता का पालन करें। आप पाते हैं कि वे पहले से ही बराबर नहीं हैं, इसलिए आप पेड़ों को मर्ज करते हैं।के बाद से 9 एक कम उच्च पेड़ को नियंत्रित करता है, हम इसे किसी के पेड़ को जोड़ने के लिए, प्राप्त करने के लिए:

.1. 
/| \ 
6 9 5 
\ \ 
    8 3 

आप देख सकते हैं यह अब जाँच करने के लिए है कि क्या दो तत्व एक ही सेट में हैं आसान है। मान लें कि आप परीक्षण करना चाहते हैं कि 8 और 3 बराबर हैं या नहीं? बस ऊपर के अपने पथों का पालन करें, और आप देखेंगे कि 8 सेट में एक सेट है, और सेट में तीन सेट 9 के द्वारा दर्शाए गए हैं। इसलिए वे असमान हैं।

हमेशा छोटे पेड़ को बड़े के नीचे रखने की ह्युरिस्टिक का उपयोग करके, आपको एक लॉग (एन) औसत मिलता है या समय मिल जाता है। विकिपीडिया लेख एक अतिरिक्त चाल बताता है, जो इसे मूल रूप से स्थिर समय बना देगा।

Answer 4

<?php 

class AliasesFinder 
{ 
    /** @var array */ 
    protected $chains; 
    /** @var array */ 
    protected $aliases; 
    protected $digits; 

    public function __construct($aliases) 
    { 
     $this->aliases = $aliases; 

     //collect all digits 
     $digits = array(); 
     foreach ($this->aliases as $alias_pair) 
     { 
      if (!in_array($alias_pair[0], $digits)) $digits[] = $alias_pair[0]; 
      if (!in_array($alias_pair[1], $digits)) $digits[] = $alias_pair[1]; 
     } 
     $this->digits = $digits; 
    } 

    public function find_all_aliases($digit, &$chain = array()) 
    { 
     //if $digit already in some chain - return, don't spend time to count another time 
     if (!empty($this->chains)) 
     { 
      foreach ($this->chains as $existing_chain) 
      { 
       if (in_array($digit, $existing_chain)) return false; 
      } 
     } 

     //$digit is part of chain already 
     $chain[] = $digit; 

     foreach ($this->aliases as $alias_pair) 
     { 
      //if alias of digit not in chain yet - add this alias-digit and all aliases of this alias-digit to chain 
      if ($digit==$alias_pair[0] && (empty($chain) || !in_array($alias_pair[1], $chain))) 
      { 
       $this->find_all_aliases($alias_pair[1], $chain); 
      } 
      elseif ($digit==$alias_pair[1] && (empty($chain) || !in_array($alias_pair[0], $chain))) 
      { 
       $this->find_all_aliases($alias_pair[0], $chain); 
      } 
     } 
     return $chain; 

    } 

    public function getChains() 
    { 
     foreach ($this->digits as $digit) 
     { 
      $aliases = $this->find_all_aliases($digit); 
      if ($aliases!==false) $this->chains[] = $aliases; 
     } 
     return $this->chains; 
    } 
} 

$aliases = Array(
    Array(1, 5), 
    Array(6, 8), 
    Array(6, 1), 
    Array(9, 3), 
); 

$finder = new AliasesFinder($aliases); 
print_r($finder->getChains());