Split set of numbers into as fewest subsets as possible of defined "interval length" algorithm

Question

consider that I have some set of numbers. For example {1, 2, 3, 7, 8, 9, 11, 15, 16}. What I need is to split this set into as fewest subsets as possible and also difference between the lowest and highest number is less than 9.
From my example set it would be for example:
{1, 2, 3, 7, 8}, {9, 11, 15, 16}
I need this to optimize the number of "read multiple registers" requests through the Modbus.
I already tried to split set into subsets with consecutive numbers and than merged them, but it's not ideal, because it returns me this:
{1, 2, 3}, {7, 8, 9, 11}, {15, 16} or {1, 2, 3}, {7, 8, 9}, {11, 15, 16}
As you can see this approach gives me three subsets instead of two.
So is there any usable algorithm?
Thanks

Answer 1

What about the greedy approach, i.e. insert elements from the left into a set, when you go over the desired difference, create a new set.

So, for 1, 2, 3, 7, 8, 9, 11, 15, 16:

You'd start off with 1.
2-1 = 1 < 9, so add 2.
3-1 = 2 < 9, so add 3.
7-1 = 6 < 9, so add 7.
8-1 = 7 < 9, so add 8.
9-1 = 8 < 9, so add 9.
11-1 = 10 > 9, so create a new set.
15-11 = 4 < 9, so add 15.
16-11 = 5 < 9, so add 16.

Output: {1, 2, 3, 7, 8, 9}, {11, 15, 16}.

Note:

If the elements aren't necessarily ordered, we can simply sort them first.

If these subsets don't have to be continuous, it doesn't make a difference, as selecting continuous sets from the ordered input is always better than non-continuous sets.

If the elements aren't necessarily ordered and the subsets must be continuous, that will change the problem a bit.

Proof of optimality:

Let S be the set assignment produced by this algorithm for some arbitrary input.

Take any set assignment T.

Let S_i be the i-th set of S.
Let T_i be the i-th set of T.

Let S_i-size be the size of the i-th set of S.
Let T_i-size be the size of the i-th set of T.

Assume S and T are different, then for some S_i and T_i, S_i-size != T_i-size. Specifically choose the first set i where the two differ.

So either S_i-size > T_i-size or S_i-size < T_i-size.

j > i is impossible, since this algorithm takes as many elements as possible from the start.

If j < i, the first element of S_i+1 will be greater than the first element of T_i+1, and since the algorithm is greedy, S_i+1 will include at least all the elements of T_i+1 not already included by S_i.

Now, because of the above, the first element of S_i+2 will similarly be greater than the first element of T_i+2, thus S_i+2 will include at least all the elements of T_i+2 not already included by previous sets of S. Similarly for the rest of the sets of S and T. Thus there are at least as many sets in T as there are in S.

Thus the set assignment produced by this algorithm can't be any worse than any other assignment. Thus it is optimal.