Yip*_*Yay 6 language-agnostic algorithm
我有一系列数字,例如:170, 205, 225, 190, 260, 130, 225, 160我必须将它们分成具有固定数量元素的集合,以便最小化集合元素之间的最大差异.
我保证如果我需要将元素拆分为元素集K,那么全局元素数等于Z * K.
对于示例K = 4,可以通过以下方式执行最佳拆分:
(1) : 130 160 170 190 (最大差异等于60)
(2) : 205 225 225 260 (最大差异等于55)
因此,此案例的全局最大差异等于60.
现在,问题是:我的假设是我可以简单地对初始数据进行排序,并从头开始将其拆分为偶数部分？如果这是正确的,我该如何证明呢？如果不是,我应该用哪种方法来解决这个问题？
假设您的数字数量始终可以被 K 整除（因此不是 4 组中的 13 个数字），这是正确的。
显然，通过排序，您可以得到彼此尽可能接近的最相似的数字。问题是，如果移动数字以使一组值更接近的最差值出现，是否会使最大差异变小？
答案是不。排序时，数字左侧的唯一值等于或小于，向左移动的数字将被较低的值包围。在造成最大差异的两个数字中，至少有一个会遇到更差的伙伴，这意味着您的最大距离会变得更高。对于右侧较大的数字，其工作方式相同。
Sorted:
[lowest, low, low, x] distance1 = x-lowest
[y, high, high, highest] distance2 = highest-y
Swapped:
[lowest, low, low, y] distance3 = y-lowest
[x, high, high, highest] distance4 = highest-x
由于 x < y （假设它们不相等，因为交换毫无意义），距离 3 > 距离 1 且距离 4 > 距离 2，这意味着情况变得更糟。
如果您在那里设置更高的值，它也会以同样的方式工作。
无论一个数字有多么不合理，在该位置放置另一个数字都会使它们更加不合理。
另一种选择是将整个子集向左移动一个空格：
[lowest, low, low, y]
[high, high, highest, x]
但这实际上和交换是一样的结果。
这就是 2 套的工作原理。
共三套：
[lowest, low, low, x]
[lowM, lowM, highM, highM]
[highM, y, high, highest]
交换 x 和 y 与之前相同。即使x与左下高非常相似甚至相等（如果中间的低和高实际上相等），y仍然高于x，使得与最低的差异更大，并且x距离最高更远。
将一堆数字向前移动：
[lowest, low, lowM, lowM]
[highM, highM, highM, y]
[x, highM, high, highest];
也许最大的区别是highM和highest之间的，而这个距离现在已经被消除了。但由于你只能通过设置一个更低的值来将其从最高值移开，所以你总是会让情况变得更糟。最高距离highest-highM 现在是highest-x，并且x < highM。
反之亦然。如果存在下一组，则 highM 可以与更接近最高的更高数字交换，但这会将 highM 与更高的数字进行交换，从而导致更大的差异。
所以是的，对数据进行排序然后将其分成相等的部分总是会给出最小的最大差异，因为更改排序的集合总是会产生更糟糕的结果。
注意：如果数字不能被 K 整除，则情况会变得更加复杂，您必须找出最差的集合，并看看是否可以将其最高或最低的数字移动到下一个或上一个集合，而不会使另一个集合变得更糟不同之处。只能将低数字与高数字交换的规则被删除，因为您可以将它们与无数字交换，因此证明这一点是一个全新的水平。