Soustrayez les chevauchements entre deux gammes sans ensembles

Ceci est plutôt laid, mais cela fonctionne pour l'exemple donné xxx

impressions: xxx

Une solution (en plus de toutes les autres solutions différentes présentées ici) consiste à utiliser un arbre d'intervalle / segment (ils sont vraiment la même chose):

http://fr.wikipedia.org/wiki/segment_tree p>

http://fr.wikipedia.org/wiki/interval_tree P>

Un grand avantage de le faire de cette façon est que c'est qu'il est Trivial pour faire des opérations booléennes arbitraires (pas seulement la soustraction) en utilisant le même morceau de code. Il existe un traitement standard de cette structure de données à De Berg. Pour effectuer une opération booléenne sur une paire d'arbres d'intervalle (y compris la soustraction), vous venez de les fusionner ensemble. Voici un code python (certes naïfs) pour le faire avec des arbres de plage déséquilibrés. Le fait qu'ils soient déséquilibrés n'a aucun effet sur le temps nécessaire pour fusionner les arbres, mais la construction arborescente ici est la partie vraiment idiote qui finit par être quadratique (à moins que la réduction ne soit exécutée par partitionnement, que je doute en quelque sorte). Quoi qu'il en soit, vous allez: P>

#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)

Le L'intervalle package peut fournir tout ce dont vous avez besoin.

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)

Voici une fonction rapide Python qui fait la soustraction, que les listes initiales soient bien formées (c.-à-d. Tournez les listes dans la liste la plus petite des plages équivalentes, triées, avant de faire la soustraction):

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)]

C'était un problème intéressant!

Je pense que cela a raison, et c'est assez compact. Il devrait fonctionner avec des gammes qui se chevauchent de toutes sortes, mais cela assume des gammes bien formées (c'est-à-dire [x, y) code> où x code>). Il utilise [x, y) code> gammes de style pour simplicité. Il est basé sur l'observation qu'il n'y a vraiment que six arrangements possibles (avec des résultats dans ()): p>

edit strong>: j'ai trouvé une représentation plus compacte: p>

>>> 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)]