अंतराल संघ

Question

मुझे एक अंतराल का प्रतिनिधित्व करने वाली कक्षा मिली है। इस वर्ग में तुलनात्मक प्रकार के दो गुण "प्रारंभ" और "अंत" हैं। अब मैं इस तरह के अंतराल के एक सेट के संघ को लेने के लिए एक कुशल एल्गोरिदम खोज रहा हूं।

अग्रिम धन्यवाद।

Answer 1

उन्हें किसी एक शब्द (उदाहरण के लिए, उदाहरण के लिए) द्वारा क्रमबद्ध करें, फिर सूची के माध्यम से अपने (दाएं हाथ) पड़ोसी के साथ ओवरलैप की जांच करें।

class tp(): 
    def __repr__(self): 
     return '(%d,%d)' % (self.start, self.end) 
    def __init__(self,start,end): 
     self.start=start 
     self.end=end 
s=[tp(5,10),tp(7,8),tp(0,5)] 
s.sort(key=lambda self: self.start) 
y=[ s[0] ] 
for x in s[1:]: 
    if y[-1].end < x.start: 
     y.append(x) 
    elif y[-1].end == x.start: 
     y[-1].end = x.end 

Answer 2

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

O (n n लॉग इन करें) + O (एन) = O (n n लॉग इन करें)

Answer 3

सब क्रमबद्ध अंक। फिर "प्रारंभ" बिंदुओं के लिए काउंटर को बढ़ाने वाली सूची के माध्यम से जाएं, और इसे "अंत" बिंदुओं के लिए घटाएं। यदि काउंटर 0 तक पहुंचता है, तो यह वास्तव में संघ में अंतराल में से एक का अंत बिंदु है।

काउंटर कभी नकारात्मक नहीं होगा, और सूची के अंत में 0 तक पहुंच जाएगा।

Answer 4

geocar द्वारा एल्गोरिथ्म में विफल रहता है जब:

s=[tp(0,1),tp(0,3)] 

मैं नहीं बहुत यकीन है, लेकिन मुझे लगता है कि यह सही तरीका है:

class tp(): 
    def __repr__(self): 
     return '(%.2f,%.2f)' % (self.start, self.end) 
    def __init__(self,start,end): 
     self.start=start 
     self.end=end 
s=[tp(0,1),tp(0,3),tp(4,5)] 
s.sort(key=lambda self: self.start) 
print s 
y=[ s[0] ] 
for x in s[1:]: 
    if y[-1].end < x.start: 
     y.append(x) 
    elif y[-1].end == x.start: 
     y[-1].end = x.end 
    if x.end > y[-1].end: 
     y[-1].end = x.end 
print y 

मैं भी घटाव के लिए इसे लागू किया:

#subtraction 
z=tp(1.5,5) #interval to be subtracted 
s=[tp(0,1),tp(0,3), tp(3,4),tp(4,6)] 

s.sort(key=lambda self: self.start) 
print s 
for x in s[:]: 
    if z.end < x.start: 
     break 
    elif z.start < x.start and z.end > x.start and z.end < x.end: 
     x.start=z.end 
    elif z.start < x.start and z.end > x.end: 
     s.remove(x) 
    elif z.start > x.start and z.end < x.end: 
     s.append(tp(x.start,z.start)) 
     s.append(tp(z.end,x.end)) 
     s.remove(x) 
    elif z.start > x.start and z.start < x.end and z.end > x.end: 
     x.end=z.start 
    elif z.start > x.end: 
     continue 

print s 

Answer 5

यह इस पी को बाहर करता है roblem हल किया गया है, कई बार - कल्पना के विभिन्न स्तरों तक पर, नामकरण (रों) के तहत जा रहा: http://en.wikipedia.org/wiki/Interval_tree, http://en.wikipedia.org/wiki/Segment_tree, और भी 'RangeTree'

(के रूप में ओ पी के सवाल के अंतराल के बड़े मायने रखता है शामिल है इन datastructures कोई फर्क)

---

अजगर पुस्तकालय चयन के अपने खुद के चुनाव के संदर्भ में

:

• परीक्षण से, मैं खोजने कर रहा हूँ क्या पूर्ण विशेषताओं और अजगर वर्तमान जा रहा है के मामले में सबसे नाखून यह (गैर बिट सड़ कि): ' इंटरमी 'और' यूनियन 'कक्षाएं SymPy से देखें: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• एक और अच्छी लग रही पसंद, एक उच्च प्रदर्शन लेकिन कम सुविधा समृद्ध विकल्प (उदाहरण के लिए। https://pypi.python.org/pypi/Banyan

अंत: एसओ पर ही चारों ओर खोज, IntervalTree, SegmentTree, RangeTree में से किसी के अधीन है, और आप जवाब मिल जाएगा/हुक आगे बहुतायत

Answer 6

चल बिन्दु सीमा हटाने) पर काम नहीं किया सी ++

#include <iostream> 
#include <algorithm> 

struct interval 
{ 
    int m_start; 
    int m_end; 
}; 

int main() 
{ 
    interval arr[] = { { 9, 10 }, { 5, 9 }, { 3, 4 }, { 8, 11 } }; 

    std::sort(
     arr, 
     arr + sizeof(arr)/sizeof(interval), 
     [](const auto& i, const auto& j) { return i.m_start < j.m_start; }); 

    int total = 0; 
    auto current = arr[0]; 
    for (const auto& i : arr) 
    { 
     if (i.m_start >= current.m_end) 
     { 
      total += current.m_end - current.m_start; 
      current = i; 
     } 
     else if (i.m_end > current.m_end) 
     { 
      current.m_end = i.m_end; 
     } 
    } 

    total += current.m_end - current.m_start; 
    std::cout << total << std::endl; 
}