كيفية تقسيم مجموعة من النطاقات المتداخلة إلى نطاقات غير متداخلة؟

Question

لنفترض أن لديك مجموعة من النطاقات:

• 0 - 100:'أ'
• 0 - 75:'ب'
• 95 - 150:"ج"
• 120 - 130:'د'

ومن الواضح أن هذه النطاقات تتداخل في نقاط معينة.كيف يمكنك تشريح هذه النطاقات لإنتاج قائمة من النطاقات غير المتداخلة، مع الاحتفاظ بالمعلومات المرتبطة بنطاقها الأصلي (في هذه الحالة، الحرف الذي يلي النطاق)؟

على سبيل المثال، ستكون نتائج ما سبق بعد تشغيل الخوارزمية:

• 0 - 75:"أ"، "ب"
• 76 - 94:'أ'
• 95 - 100:"أ"، "ج"
• 101 - 119:"ج"
• 120 - 130:'ج'، 'د'
• 131 - 150:"ج"

Answer 1

كان لدي نفس السؤال عند كتابة برنامج لمزج العينات الصوتية (المتداخلة جزئيًا).

ما فعلته هو إضافة "حدث البدء" و"حدث الإيقاف" (لكل عنصر) إلى القائمة، وفرز القائمة حسب النقطة الزمنية، ثم معالجتها بالترتيب.يمكنك أن تفعل الشيء نفسه، باستثناء استخدام نقطة عدد صحيح بدلاً من الوقت، وبدلاً من مزج الأصوات، ستضيف رموزًا إلى المجموعة المقابلة لنطاق ما.ما إذا كنت تريد إنشاء نطاقات فارغة أو حذفها فقط سيكون أمرًا اختياريًا.

Edit ربما بعض التعليمات البرمجية ...

# input = list of (start, stop, symbol) tuples
points = [] # list of (offset, plus/minus, symbol) tuples
for start,stop,symbol in input:
    points.append((start,'+',symbol))
    points.append((stop,'-',symbol))
points.sort()

ranges = [] # output list of (start, stop, symbol_set) tuples
current_set = set()
last_start = None
for offset,pm,symbol in points:
    if pm == '+':
         if last_start is not None:
             #TODO avoid outputting empty or trivial ranges
             ranges.append((last_start,offset-1,current_set))
         current_set.add(symbol)
         last_start = offset
    elif pm == '-':
         # Getting a minus without a last_start is unpossible here, so not handled
         ranges.append((last_start,offset-1,current_set))
         current_set.remove(symbol)
         last_start = offset

# Finish off
if last_start is not None:
    ranges.append((last_start,offset-1,current_set))

من الواضح أنه لم يتم اختباره تمامًا.

Answer 2

أود أن أقول إنشاء قائمة بنقاط النهاية وفرزها، وكذلك فهرسة قائمة النطاقات حسب نقاط البداية والنهاية.ثم قم بالتكرار عبر قائمة نقاط النهاية التي تم فرزها، ولكل منها، تحقق من النطاقات لمعرفة أي منها يبدأ/يتوقف عند تلك النقطة.

ربما يتم تمثيل هذا بشكل أفضل في الكود ...إذا تم تمثيل نطاقاتك بواسطة صفوف:

ranges = [(0,100,'a'),(0,75,'b'),(95,150,'c'),(120,130,'d')]
endpoints = sorted(list(set([r[0] for r in ranges] + [r[1] for r in ranges])))
start = {}
end = {}
for e in endpoints:
    start[e] = set()
    end[e] = set()
for r in ranges:
    start[r[0]].add(r[2])
    end[r[1]].add(r[2])
current_ranges = set()
for e1, e2 in zip(endpoints[:-1], endpoints[1:]):
    current_ranges.difference_update(end[e1])
    current_ranges.update(start[e1])
    print '%d - %d: %s' % (e1, e2, ','.join(current_ranges))

على الرغم من النظر إلى هذا الأمر بأثر رجعي، إلا أنني سأفاجأ إذا لم تكن هناك طريقة أكثر كفاءة (أو على الأقل ذات مظهر أنظف) للقيام بذلك.

Answer 3

ما تصفه هو مثال على نظرية المجموعات.للحصول على خوارزمية عامة لحساب الاتحادات والتقاطعات والاختلافات بين المجموعات، انظر:

www.gvu.gatech.edu/~jarek/graphics/papers/04PolygonBooleansMargalit.pdf

في حين أن الورقة تستهدف الرسومات، إلا أنها تنطبق على نظرية المجموعات العامة أيضًا.ليست مادة قراءة خفيفة تمامًا.

Answer 4

كود مزيف:

unusedRanges = [ (each of your ranges) ]
rangesInUse = []
usedRanges = []
beginningBoundary = nil

boundaries = [ list of all your ranges' start and end values, sorted ]
resultRanges = []

for (boundary in boundaries) {
    rangesStarting = []
    rangesEnding = []

    // determine which ranges begin at this boundary
    for (range in unusedRanges) {
        if (range.begin == boundary) {
            rangesStarting.add(range)
        }
    }

    // if there are any new ones, start a new range
    if (rangesStarting isn't empty) {
        if (beginningBoundary isn't nil) {
            // add the range we just passed
            resultRanges.add(beginningBoundary, boundary - 1, [collected values from rangesInUse])
        }

        // note that we are starting a new range
        beginningBoundary = boundary

        for (range in rangesStarting) {
            rangesInUse.add(range)
            unusedRanges.remove(range)
        }
    }

    // determine which ranges end at this boundary
    for (range in rangesInUse) {
        if (range.end == boundary) {
            rangesEnding.add(range)
        }
    }

    // if any boundaries are ending, stop the range
    if (rangesEnding isn't empty) {
        // add the range up to this boundary
        resultRanges.add(beginningBoundary, boundary, [collected values from rangesInUse]

        for (range in rangesEnding) {
            usedRanges.add(range)
            rangesInUse.remove(range)
        }

        if (rangesInUse isn't empty) {
            // some ranges didn't end; note that we are starting a new range
            beginningBoundary = boundary + 1
        }
        else {
            beginningBoundary = nil
        }
    }
}

اختبار الوحدة:

في النهاية، يجب أن تحتوي resultRanges على النتائج التي تبحث عنها، ويجب أن تكون unusedRanges وrangesInUse فارغة، ويجب أن تكون beginBoundary صفرًا، ويجب أن تحتوي useRanges على ما تحتوي عليه النطاقات غير المستخدمة (ولكن يتم فرزها حسب range.end).

Answer 5

تم اختبار إجابة مشابهة لـ Edmunds، بما في ذلك دعم الفواصل الزمنية مثل (1,1):

class MultiSet(object):
    def __init__(self, intervals):
        self.intervals = intervals
        self.events = None

    def split_ranges(self):
        self.events = []
        for start, stop, symbol in self.intervals:
            self.events.append((start, True, stop, symbol))
            self.events.append((stop, False, start, symbol))

        def event_key(event):
            key_endpoint, key_is_start, key_other, _ = event
            key_order = 0 if key_is_start else 1
            return key_endpoint, key_order, key_other

        self.events.sort(key=event_key)

        current_set = set()
        ranges = []
        current_start = -1

        for endpoint, is_start, other, symbol in self.events:
            if is_start:
                if current_start != -1 and endpoint != current_start and \
                       endpoint - 1 >= current_start and current_set:
                    ranges.append((current_start, endpoint - 1, current_set.copy()))
                current_start = endpoint
                current_set.add(symbol)
            else:
                if current_start != -1 and endpoint >= current_start and current_set:
                    ranges.append((current_start, endpoint, current_set.copy()))
                current_set.remove(symbol)
                current_start = endpoint + 1

        return ranges


if __name__ == '__main__':
    intervals = [
        (0, 100, 'a'), (0, 75, 'b'), (75, 80, 'd'), (95, 150, 'c'), 
        (120, 130, 'd'), (160, 175, 'e'), (165, 180, 'a')
    ]
    multiset = MultiSet(intervals)
    pprint.pprint(multiset.split_ranges())


[(0, 74, {'b', 'a'}),
 (75, 75, {'d', 'b', 'a'}),
 (76, 80, {'d', 'a'}),
 (81, 94, {'a'}),
 (95, 100, {'c', 'a'}),
 (101, 119, {'c'}),
 (120, 130, {'d', 'c'}),
 (131, 150, {'c'}),
 (160, 164, {'e'}),
 (165, 175, {'e', 'a'}),
 (176, 180, {'a'})]