How to join integers intervals in python?

Question

I have used the module intervals (http://pyinterval.readthedocs.io/en/latest/index.html)

And created an interval from a set or start, end tuples:

intervals = interval.interval([1,8], [7,10], [15,20])

Which result in interval([1.0, 10.0], [15.0, 20.0]) as the [1,8] and [7,10] overlaps.

But this module interprets the values of the pairs as real numbers, so two continuous intervals in integers will not be joined together.

Example:

intervals = interval.interval([1,8], [9,10], [11,20]) 

results in: interval([1.0, 8.0], [9.0, 10.0], [11.0, 20.0])

My question is how can I join this intervals as integers and not as real numbers? And in the last example the result would be interval([1.0, 20.0])

Amortizement

not necessarily, you're missing [8,9] and [10,11]. For the intervals to overlap you need an intersection region or point. – Reichenberg

I thought my question was clear enough, im looking for a way to join discrete intervals based on natural numbers, not real numbers – Amortizement

Answer 1

The intervals module pyinterval is used for real numbers, not for integers. If you want to use objects, you can create an integer interval class or you can also code a program to join integer intervals using the interval module:

def join_int_intervlas(int1, int2):
    if int(int1[-1][-1])+1 >= int(int2[-1][0]):
        return interval.interval([int1[-1][0], int2[-1][-1]])
    else:
        return interval.interval()

Passageway

What are the int1, int2 objects? I dont understand the int1[-1][-1] or the int2[-1][0]. Are you trying to access the last position of the first element in the int1 and the first position of the last element in the int2? And if so, what would it be its meaning? – Amortizement

int1 and int2 are the intervals. You are trying to join two integer intervals. int[-1][-1] is the last number of the interval. and [-1][0] is the first element of the interval. I'm trying to "connect" the integer intervals. Pyinterval is a real number modules, so if you want to connect two integer intervals, you have to take out decimal difference (from 8.1 to 8.999) between the last number of the first interval and the last one, that's why I sum +1. This is a workaround for integer numbers. – Passageway

I understand now, the int1 and int2 are intervals from pyintervals. Thanks – Amortizement

Answer 2

I believe you can use pyintervals for integer intervals too by adding interval([-0.5, 0.5]). With your example you get

In[40]:  interval([1,8], [9,10], [11,20]) + interval([-0.5, 0.5])
Out[40]: interval([0.5, 20.5])

Zarger

Answer 3

This takes a list of tuples like l = [(25,24), (17,18), (5,9), (24,16), (10,13), (15,19), (22,25)]

# Idea by Ben Voigt in https://mcmap.net/q/730610/-a-container-for-integer-intervals-such-as-rangeset-for-c
def sort_condense(ivs):
    if len(ivs) == 0:
        return []
    if len(ivs) == 1:
        if ivs[0][0] > ivs[0][1]:
            return [(ivs[0][1], ivs[0][0])]
        else:
            return ivs
    eps = []
    for iv in ivs:
        ivl = min(iv)
        ivr = max(iv)
        eps.append((ivl, False))
        eps.append((ivr, True))
    eps.sort()
    ret = []
    level = 0
    i = 0
    while i < len(eps)-1:
        if not eps[i][1]:
            level = level+1
            if level == 1:
                left = eps[i][0]
        else:
            if level == 1:
                if not eps[i+1][1]
                   and eps[i+1][0] == eps[i][0]+1:
                    i = i+2
                    continue
                right = eps[i][0]
                ret.append((left, right))
            level = level-1
        i = i+1
    ret.append((left, eps[len(eps)-1][0]))
    return ret

In [1]: sort_condense(l)
Out[1]: [(5, 13), (15, 25)]

The idea is outlined in Ben Voigt's answer to A container for integer intervals, such as RangeSet, for C++

Python is not my main language, sorry.

Skirr

Answer 4

I came up with the following program:

ls = [[1,8], [7,10], [15,20]]
ls2 = []
prevList = ls[0]
for lists in ls[1:]:
    if lists[0] <= prevList[1]+1:
        prevList = [prevList[0], lists[1]]
    else:
        ls2.append(prevList)
        prevList = lists
ls2.append(prevList)

print ls2 # prints [[1, 10], [15, 20]]

It permutes through all lists and checks if the firsy element of each list is less than or equal to the previous element + 1. If so, it clubs the two.

Perron

Yeah, it kinda works over the already created interval object with the sorted intervals, it will be a two step then, because I might encounter a really big number of intervals, so im going to need pyintervals still, thank you – Amortizement