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

Question

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