CODEWITHSUNDEEP
pythonpython-3.xlistintegerintervals
Guillaume
Guillaume

Reputation: 115

Generate every possible intervals of integers

Despite my researches, I have found no solution to my issue. Thank you for your help !

Let a and b, two integers. I want to generate all sub intervals of integers no matter their lengths between this two integers.

For example, let a=2 and b=5, the result I tried to obtained is:

[
 [[2],[3],[4],[5]
 [[2,5]],
 [[2],[3,5]],
 [[2],[3,4],[5]],
 [[2],[3],[4,5]],
 [[2,3],[4,5]],
 [[2,3],[4],[5]],
 [[2,4],[5]]
]

Thank you for your help,

Best regards !

Upvotes: 3

Views: 402

Answers (2)

markuscosinus
markuscosinus

Reputation: 2267

I wrote a method that does what you asked for. It's not very beatiful to look at, but it does the job.

def subIntervals(a,b):
    outputList = [[[a]]]
    for n in range(a+1, b+1):
        newOutputList = []
        for e in outputList:
            newOutputList.append(e + [[n]])
            newOutputList.append(e[:-1] + [[e[-1][0], n]])
        outputList = newOutputList
    return outputList

I will add an explanation if needed.

Upvotes: 1

blhsing
blhsing

Reputation: 106553

You can use a function that yields intervals from numbers closest to a (which is a itself) to b, and then recursively yields the intervals from a + 1 to b:

def intervals(a, b):
    if a > b:
        yield []
    for i in range(a, b + 1):
        for interval in intervals(i + 1, b):
            yield [[a] if a == i else [a, i], *interval]

so that:

list(intervals(2, 5))

returns:

[[[2], [3], [4], [5]],
 [[2], [3], [4, 5]],
 [[2], [3, 4], [5]],
 [[2], [3, 5]],
 [[2, 3], [4], [5]],
 [[2, 3], [4, 5]],
 [[2, 4], [5]],
 [[2, 5]]]

Upvotes: 3

Related Questions