Stability of the main algorithm

Question

I have a sequence of numbers, for example: 170, 205, 225, 190, 260, 130, 225, 160 , and I have to break them into sets with a fixed number of elements, so that the maximum difference between the elements of the sets is minimized .

I have a guarantee that if I need to divide elements into groups of elements K , then the global number of elements is Z * K

In the example with K = 4 optimal splitting can be performed as follows:

(1) : 130 160 170 190 (maximum difference is 60)

(2) : 205 225 225 260 (maximum difference is 55)

Thus, the global maximum difference for this case is 60.

---

Now the question is: is my assumption that I can just sort the source data and split it into even parts, starting from the very beginning? If this is correct, how can I prove it? And if it is not, what approach should I use to solve this problem?

Answer 1

Assuming that your number of numbers can always be divided exactly by K (therefore not 13 numbers in 4 sets), this is correct.

Through sorting, you obviously get the most similar numbers as close to each other as possible. The question is, if numbers move to cast the worst value into a set with closer values, does the maximum difference decrease?

The answer is no. When sorting, the only values ​​to the left of the number are equal to or lower, the number that will move to the left will be surrounded by lower values. Of the two numbers that caused the maximum difference, at least one will get an even worse partner, which means your maximum distance will become higher. It works the same way with higher numbers on the right.

 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 

Since x <y (for example, they are not equal, since the exchange will be pointless), distance3> distance1 and distance4> distance2, which means that everything has deteriorated.

This works the same if you post a higher value there.

No matter how far from the number, adding another number to this place will make them more inactive.

Another option is to move the entire subset to one remaining space:

 [lowest, low, low, y] [high, high, highest, x] 

But this is actually the same result as the exchange.

So how does this work with two sets.

With three sets:

 [lowest, low, low, x] [lowM, lowM, highM, highM] [highM, y, high, highest] 

The permutation of x and y is the same as before. Even if x is very similar or even equal to the lower left high (if the average lows and highs are actually equal), y is even higher than x, making the difference to the lowest value, and x is greater than the highest.

Move a bunch of numbers forward:

 [lowest, low, lowM, lowM] [highM, highM, highM, y] [x, highM, high, highest]; 

Perhaps the biggest difference was between highM and height, and now this distance is removed. But since you can only move it away from the highest by setting an even lower value there, you always make it worse. The highest distance of the highest level M is now the highest - x, and x <highM.

It still works the other way around. If there was the next set, highM could be swapped with a higher number closer to the highest, but this would put highM with even larger numbers, which would lead to an even greater difference.

So, sorting the data and then dividing it in equal parts always gives the minimum maximum difference, because changing the sorted sets always gives the worst results.

Note. If the numbers are not divisible by K, it becomes more complicated, you will have to figure out the worst set and see if you can transfer its highest or low number to the next or previous set, without making the other set the worst difference. The rule that you can only change by low numbers with large numbers is deleted, since you can change them without numbers, so the proof is that this is a whole new level.

Answer 2

If the starting sequence is sorted, then the adjacent numbers should have the smallest difference.

In addition, the elements at the beginning and end of the sequence should have the greatest difference.

As a result, any “cut” of a sequence including the last element and the first element cannot be part of the solution, since it includes a difference that is not minimal.

Thus, the separation must be done by dividing the sequence of numbers into even parts, starting from the beginning.

It seems to me that your approach is correct, but I can not come up with a more formal proof of this.

Answer 3

Naturally, you get the smallest difference between pairs of numbers by sorting them. You can get the sets with the least differences by simply dividing the sorted numbers.

In some cases, you can switch between sets without increasing the maximum number of each set, so there can be more than one way of dividing numbers into sets that give the same maximum difference. However, you cannot switch numbers between sets to decrease the maximum of any of them without increasing the maximum of another set.

If, for example, you have sets 1,3,4,5 and 6,7,8,10 , then you can switch 5 and 6 without increasing the maximum difference in any group.

If you need the smallest average of the differences, you can sacrifice the maximum difference in one set to reduce the difference in the other set.