algorithm - 将一组数字拆分为定义的“间隔长度”算法尽可能少的子集

Question

考虑到我有一些数字。例如 {1, 2, 3, 7, 8, 9, 11, 15, 16}。我需要将此集合拆分为尽可能少的子集，并且最低和最高数字之间的差异小于 9。
从我的示例集中，例如：
{1、2、3、7、8}， {9, 11, 15, 16}
我需要这个来优化通过 Modbus 的“读取多个寄存器”请求的数量。
我已经尝试将集合拆分为具有连续数字的子集，然后将它们合并，但这并不理想，因为它返回给我：
{1, 2, 3}, {7, 8, 9, 11}, {15, 16}或 {1, 2, 3}, {7, 8, 9}, {11, 15, 16}
如您所见，这种方法给了我三个子集而不是两个。
那么有什么可用的算法吗？
谢谢

Answer 1

贪心方法怎么样，即从左侧插入元素到集合中，当您检查所需的差异时，创建一个新集合。

所以，对于1, 2, 3, 7, 8, 9, 11, 15, 16：

您将从 1.
2-1 = 1 < 9 开始，因此添加 2.
3-1 = 2 < 9，因此添加 3.
7-1 = 6 < 9，因此添加 7.
8-1 = 7 < 9，所以加
8。9-1 = 8 < 9，所以加
9。11-1 = 10 > 9，所以创建一个新集合。
15-11 = 4 < 9，所以加
15。16-11 = 5 < 9，所以加 16。

输出：{1, 2, 3, 7, 8, 9}, {11, 15, 16}。

笔记：

如果元素不一定是有序的，我们可以简单地先对它们进行排序。

如果这些子集不必是连续的，那也没什么区别，因为从有序输入中选择连续集总是比非连续集好。

如果元素不一定是有序的并且子集必须是连续的，那将稍微改变问题。

最优性证明：

令 S 是该算法为某些任意输入生成的集合分配。

接受任何集合分配 T。

令 S _i为 S 的第 i 个集合。
令 T _i为 T 的第 i 个集合。

令 S _i-size为第 i 个 S 集合的大小。
令 T _i-size为第 i 个 T 集合的大小。

假设 S 和 T 不同，那么对于某些 S _i和 T _i， S _i-size != T _i-size。具体选择i两者不同的第一组。

所以要么 S _i-size > T _i-size要么 S _i-size < T _i-size。

j > i 是不可能的，因为这个算法从一开始就需要尽可能多的元素。

如果 j < i，则 S _i+1的第一个元素将大于 T _i+1的第一个元素，并且由于算法是贪婪的，因此 S _i+1将至少包括 T _i+1的所有元素而不是已经包含在 S _i中。

现在，由于上述原因，S _i+2的第一个元素将类似地大于 T _i+2的第一个元素，因此 S _i+2将至少包括 T _i+2中尚未包含的所有元素S 的先前集合。对于 S 和 T 的其余集合也是如此。因此，T 中的集合至少与 S 中的集合一样多。

因此，该算法产生的集合赋值不会比任何其他赋值差。因此它是最优的。