Вычесть перекрытия между двумя диапазонами без наборов

Пакет interval может предоставить все, что вам нужно.

from interval import Interval, IntervalSet
r1 = IntervalSet([Interval(1, 1000), Interval(1100, 1200)])
r2 = IntervalSet([Interval(30, 50), Interval(60, 200), Interval(1150, 1300)])
print(r1 - r2)

>>> [1..30),(50..60),(200..1000],[1100..1150)

Одно из решений (в дополнение ко всем другим решениям, представленным здесь) состоит в использовании дерева интервалов/сегментов (на самом деле это одно и то же):

http://en.wikipedia.org/wiki/дерево_сегментов

http://en.wikipedia.org/wiki/Interval_tree

Одним из больших преимуществ такого подхода является простота выполнения произвольных логических операций (а не только вычитания) с использованием одного и того же фрагмента кода. У де Берга есть стандартная трактовка этой структуры данных. Чтобы выполнить любую логическую операцию над парой деревьев интервалов (включая вычитание), вы просто объединяете их вместе. Вот некоторый (по общему признанию наивный) код Python для выполнения этого с несбалансированными деревьями диапазонов. Тот факт, что они несбалансированы, не влияет на время, необходимое для слияния деревьев, однако построение дерева здесь - действительно глупая часть, которая в конечном итоге становится квадратичной (если только сокращение не выполняется путем разбиения, в чем я почему-то сомневаюсь). В любом случае, вот:

class IntervalTree:
    def __init__(self, h, left, right):
        self.h = h
        self.left = left
        self.right = right

def merge(A, B, op, l=-float("inf"), u=float("inf")):
    if l > u:
        return None
    if not isinstance(A, IntervalTree):
        if isinstance(B, IntervalTree):
            opT = op
            A, B, op = B, A, (lambda x, y : opT(y,x))
        else:
            return op(A, B)
    left = merge(A.left, B, op, l, min(A.h, u))
    right = merge(A.right, B, op, max(A.h, l), u)
    if left is None:
        return right
    elif right is None or left == right:
        return left
    return IntervalTree(A.h, left, right)

def to_range_list(T, l=-float("inf"), u=float("inf")):
    if isinstance(T, IntervalTree):
        return to_range_list(T.left, l, T.h) + to_range_list(T.right, T.h, u)
    return [(l, u-1)] if T else []

def range_list_to_tree(L):
    return reduce(lambda x, y : merge(x, y, lambda a, b: a or b), 
        [ IntervalTree(R[0], False, IntervalTree(R[1]+1, True, False)) for R in L ])        

Я написал это быстро и не так много тестировал, поэтому могут быть ошибки. Также обратите внимание, что этот код будет работать с произвольными логическими операциями, а не только с различиями (вы просто передаете их в качестве аргумента операции при слиянии). Временная сложность оценки любого из них линейна по размеру выходного дерева (что также совпадает с количеством интервалов в результате). В качестве примера я запустил его в случае, который вы предоставили:

#Example:
r1 = range_list_to_tree([ (1, 1000), (1100, 1200) ])
r2 = range_list_to_tree([ (30, 50), (60, 200), (1150, 1300) ])
diff = merge(r1, r2, lambda a, b : a and not b)
print to_range_list(diff)

И я получил следующий вывод:

[(1, 29), (51, 59), (201, 1000), (1100, 1149)]

Что, кажется, согласуется с тем, что вы ожидаете. Теперь, если вы хотите выполнить некоторые другие логические операции, вот как это будет работать, используя ту же функцию:

#Intersection
merge(r1, r2, lambda a, b : a and b)

#Union
merge(r1, r2, lambda a, b : a or b)

#Xor
merge(r1, r2, lambda a, b : a != b)

Это была интересная задача!

Я думаю, что это правильно, и это довольно компактно. Он должен работать с перекрывающимися диапазонами всех видов, но предполагает правильно сформированные диапазоны (т. е. [x, y), где x < y). Он использует диапазоны стилей [x, y) для простоты. Он основан на наблюдении, что на самом деле существует только шесть возможных вариантов (с результатами в ()):

Изменить: я нашел более компактное представление:

(s1 e1)  s2 e2
(s1 s2)  e1 e2
(s1 s2) (e2 e1)

 s2 e2  (s1 e1)
 s2 s1  (e2 e1)
 s2 s1   e1 e2 ()

Учитывая отсортированный список конечных точек, если endpoints[0] == s1, то первые две конечные точки должны быть в результате. Если endpoints[3] == e1, то в результате должны быть две последние конечные точки. Если ни того, ни другого, то результата быть не должно.

Я особо не проверял, так что вполне возможно, что что-то не так. Пожалуйста, дайте мне знать, если вы найдете ошибку!

import itertools

def range_diff(r1, r2):
    s1, e1 = r1
    s2, e2 = r2
    endpoints = sorted((s1, s2, e1, e2))
    result = []
    if endpoints[0] == s1:
        result.append((endpoints[0], endpoints[1]))
    if endpoints[3] == e1:
        result.append((endpoints[2], endpoints[3]))
    return result

def multirange_diff(r1_list, r2_list):
    for r2 in r2_list:
        r1_list = list(itertools.chain(*[range_diff(r1, r2) for r1 in r1_list]))
    return r1_list

Протестировано:

>>> r1_list = [(1, 1001), (1100, 1201)]
>>> r2_list = [(30, 51), (60, 201), (1150, 1301)]
>>> print multirange_diff(r1_list, r2_list)
[(1, 30), (51, 60), (201, 1001), (1100, 1150)]

Я думаю, что неправильно понял вопрос, но этот код работает, если r2 является подмножеством r1

class RangeSet:
    def __init__(self, elements):
        self.ranges = list(elements)

    def __iter__(self):
        return iter(self.ranges)

    def __repr__(self):
        return 'RangeSet: %r' % self.ranges

    def has(self, tup):
        for pos, i in enumerate(self.ranges):
            if i[0] <= tup[0] and i[1] >= tup[1]:
                return pos, i
        raise ValueError('Invalid range or overlapping range')

    def minus(self, tup):
        pos, (x,y) = self.has(tup)
        out = []
        if x < tup[0]:
            out.append((x, tup[0]-1))
        if y > tup[1]:
            out.append((tup[1]+1, y))
        self.ranges[pos:pos+1] = out

    def __sub__(self, r):
        r1 = RangeSet(self)
        for i in r: r1.minus(i)
        return r1

    def sub(self, r): #inplace subtraction
        for i in r:
            self.minus(i)

затем вы делаете:

Обновление: обратите внимание, что последний интервал r2 отличается от того, что я имел в виду.

>>> r1 = RangeSet(((1, 1000), (1100, 1200)))
>>> r2 = RangeSet([(30, 50), (60, 200), (1150, 1200)])
>>> r1 - r2
RangeSet: [(1, 29), (51, 59), (201, 1000), (1100, 1149)]
>>> r1.sub(r2)
>>> r1
RangeSet: [(1, 29), (51, 59), (201, 1000), (1100, 1149)]

Вот быстрая функция Python, которая выполняет вычитание независимо от того, правильно ли сформированы исходные списки (т.е. превращает списки в наименьший список эквивалентных диапазонов, отсортированных перед выполнением вычитания):

def condense(l):
    l = sorted(l)
    temp = [l.pop(0)]
    for t in l:
        if t[0] <= temp[-1][1]:
            t2 = temp.pop()
            temp.append((t2[0], max(t[1], t2[1])))
        else:
            temp.append(t)
    return temp

def setSubtract(l1, l2):
    l1 = condense(l1)
    l2 = condense(l2)
    i = 0
    for t in l2:
        while t[0] > l1[i][1]:
            i += 1
            if i >= len(l1):
                break
        if t[1] < l1[i][1] and t[0] > l1[i][0]:
            #t cuts l1[i] in 2 pieces
            l1 = l1[:i] + [(l1[i][0], t[0] - 1), (t[1] + 1, l1[i][1])] + l1[i + 1:]
        elif t[1] >= l1[i][1] and t[0] <= l1[i][0]:
            #t eliminates l1[i]
            l1.pop(i)
        elif t[1] >= l1[i][1]:
            #t cuts off the top end of l1[i]
            l1[i] = (l1[i][0], t[0] - 1)
        elif t[0] <= l1[i][0]:
            #t cuts off the bottom end of l1[i]
            l1[i] = (t[1] + 1, l1[i][1])
        else:
            print "This shouldn't happen..."
            exit()
    return l1

r1 = (1, 1000), (1100, 1200)
r2 = (30, 50), (60, 200), (1150, 1300)
setSubtract(r1, r2) #yields [(1, 29), (51, 59), (201, 1000), (1100, 1149)]

Забавный вопрос! Еще одна реализация, хотя у вас уже есть много. Интересно было сделать! Включает некоторые дополнительные «украшения», чтобы сделать то, что я делаю, более явным.

import itertools

def flatten_range_to_labeled_points(input_range,label):
    range_with_labels = [((start,'start_%s'%label),(end,'end_%s'%label)) for (start,end) in input_range]
    flattened_range = list(reduce(itertools.chain,range_with_labels))
    return flattened_range 

def unflatten_range_remove_labels(input_range):
    without_labels = [x for (x,y) in input_range]
    grouped_into_pairs = itertools.izip(without_labels[::2], without_labels[1::2])
    return grouped_into_pairs

def subtract_ranges(range1, range2):
    range1_labeled = flatten_range_to_labeled_points(range1,1)
    range2_labeled = flatten_range_to_labeled_points(range2,2)
    all_starts_ends_together = sorted(range1_labeled + range2_labeled)
    in_range1, in_range2 = False, False
    new_starts_ends = []
    for (position,label) in all_starts_ends_together:
        if label=='start_1':
            in_range1 = True
            if not in_range2:
                new_starts_ends.append((position,'start'))
        elif label=='end_1':
            in_range1 = False
            if not in_range2:
                new_starts_ends.append((position,'end'))
        elif label=='start_2':
            in_range2 = True
            if in_range1:
                new_starts_ends.append((position-1,'end'))
        elif label=='end_2':
            in_range2 = False
            if in_range1:
                new_starts_ends.append((position+1,'start'))
    # strip the start/end labels, they're not used, I just appended them for clarity
    return unflatten_range_remove_labels(new_starts_ends)

Я получаю правильный вывод:

r1 = (1, 1000), (1100, 1200)
r2 = (30, 50), (60, 200), (1150, 1300)
>>> subtract_ranges(r1,r2)
[(1, 29), (51, 59), (201, 1000), (1100, 1149)]

это довольно уродливо, но это работает для данного примера

def minus1(a,b):
    if (b[0] < a[0] and b[1] < a[0]) or (a[1] < b[0] and a[1] < b[1]):
        return [a] # doesn't overlap
    if a[0]==b[0] and a[1]==b[1]:
        return [] # overlaps exactly
    if b[0] < a[0] and a[1] < b[1]:
        return [] # overlaps completely
    if a[0]==b[0]:
        return [(b[1]+1,a[1])] # overlaps exactly on the left
    if a[1]==b[1]:
        return [(a[0],b[0]-1)] # overlaps exactly on the right 
    if a[0] < b[0] and b[0] < a[1] and a[1] < b[1]:
        return [(a[0],b[0]-1)] # overlaps the end
    if a[0] < b[1] and b[1] < a[1] and b[0] < a[0]:
        return [(b[1]+1,a[1])] # overlaps the start
    else:
        return [(a[0],b[0]-1),(b[1]+1,a[1])] # somewhere in the middle

def minus(r1, r2):
    # assume r1 and r2 are already sorted
    r1 = r1[:]
    r2 = r2[:]
    l = []
    v = r1.pop(0)
    b = r2.pop(0)
    while True:
        r = minus1(v,b)
        if r:
            if len(r)==1:
                if r[0] == v:
                    if v[1] < b[0] and v[1] < b[1]:
                        l.append(r[0])
                        if r1:
                            v = r1.pop(0)
                        else:
                            break
                    else:
                        if r2:
                            b = r2.pop(0)
                        else:
                            break
                else:
                    v = r[0]
            else:
                l.append(r[0])
                v = r[1]
                if r2:
                    b = r2.pop(0)
                else:
                    l.append(v)
                    break
        else:
            if r1:
                v = r1.pop(0)
            else:
                break
            if r2:
                b = r2.pop(0)
            else:
                l.append(v)
                l.extend(r1)
                break
    return l

r1 = [(1, 1000), (1100, 1200)]
r2 = [(30, 50), (60, 200), (1150, 1300)]

print minus(r1,r2)

печатает:

[(1, 29), (51, 59), (201, 1000), (1100, 1149)]