How can I efficiently generate the shortest list of arguments for the range() function that will generate a given list of integers?

I ran into an interesting problem at work when trying to generate the inputs for an API given the expected output. I've tried to formalize and anonymize the problem below. I've been trying to design a fast algorithm that works here but I'm a little stuck. Thanks in advance for the help! I'm not an experienced question writer so please feel free to edit this to make it clearer. I'll do my best to answer any clarifying questions.

Background

In python 2.7, the range function takes 3 arguments (start, stop, and step) and returns a list of integers.


The full form returns a list of plain integers [start, start + step,
start + 2 step, ...]. If step is positive, the last element is the largest start + i step less than stop; if step is negative, the last element is the smallest start + i * step greater than stop.

Documentation

Examples

>>> range(0, 30, 5)
[0, 5, 10, 15, 20, 25]
>>> range(0, 10, 3)
[0, 3, 6, 9]

Problem

Given a list of positive integers, I, generate a list of 3-tuples that when fed into the range() function that will generate the same set of integers as I. The answer list must be the minimum possible length. If more than one minimum length solution exists, return any of the solutions.

Examples

Input: [1, 2, 3]
Output: [(1, 4, 1)]

Input: [1, 2, 3, 5, 7, 9]
Output: [(1, 4, 1), (5, 10, 2)] or [(1, 10, 2), (2, 3, 1)]

Input: [1, 2, 4, 5, 6, 11, 12, 13]
Output: [(1, 3, 1), (4, 7, 1), (11, 14, 1)]

I'm assuming the input does not have duplicates, e.g. not [1, 2, 2, 5].

No, an efficient (polynomial time) algorithm does not exist to our best knowledge, as per "Covering a set with arithmetic progressions is NP-complete" by Lenwood S.Health.

But we can make a recursive algorithm regardless, it will just be exponential time as our input grows.

Note that the first element not covered by previous ranges must be the start of the next range. Furthermore, you can always cover at least two elements with each range. And even better, the second element you choose to cover with a range also fully determines that range. The stop condition doesn't really matter - you'd just stop when the next element generated wouldn't be in the set.

With this information you can write a recursive algorithm (which assumes l is given sorted):

def cover_ap(l):
if not l: return []
if len(l) == 1: return [(l[0], l[0])]

candidates = []
a = l[0]
for b in l[1:]:
ap = [a, b]
step = b - a
k = b + step
while step > 0 and k in l:
ap.append(k)
k += step
stop = ap[-1] + 1

remain = sorted(set(l) - set(ap))
candidates.append([(a, stop, step)] + cover_ap(remain))

return min(candidates, key=len)


StackExchange Computer Science Q#97294, answer score: 3