Divide the set into k groups with a minimum number of moves

Question

You have a set of n objects for which integer positions are given. A group of objects is a set of objects in the same position (not all objects are in this position: there can be several groups in one position). Objects can move left or right, and the goal is to move these objects to form groups of k, and to do this with minimal distance movement.

For instance:

• With initial positions in [4,4,7] and k = 3: the minimum cost is 0.
• [4,4,7] and k = 2: the minimum cost is 0
• [1,2,5,7] and k = 2: the minimum cost is 1 + 2 = 3

I am trying to use a greedy approach (by calculating which step will be the shortest), but this will not work, because each movement includes two elements that can be moved anyway. I have not yet been able to formulate an approach to dynamic programming, but I am working on it.

Answer 1

This problem is a one-dimensional instance of the k-medians problem, which can be formulated as follows. Given the set of points x_1 ... x_n, we divide these points into k sets S_1 ... S_k and choose k locations y_1 ... y_k in such a way as to minimize the sum over all x_i | x_i - y_f (i) |, where y_f (i) is the corresponding location of the set to which x_i is assigned.

Due to the fact that the median is the population minimizer for the absolute distance (i.e., the norm L_1) , it follows that each location y_j will be the median of the elements x in the corresponding set S_j (hence the name of the k-median). Since you are looking at integer values, it is technically possible that if S_j contains an even number of elements, the median may not be an integer, but in such cases, choosing either the next integer above or below the median will give the same amount of absolute distances.

The standard heuristic for solving k-medians (and the related and more general k-means problem) is iterative, but it is not guaranteed to get an optimal or even good solution. The solution of the k-median problem for general metric spaces is NP-complicated, and finding effective approximations for k-medians is an open research problem. For example, the approximation of "k-medians" in Google, for example, will lead to a handful of articles giving approximation schemes. http://www.cis.upenn.edu/~sudipto/mypapers/kmedian_jcss.pdf http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arr-clustering.pdf

In one dimension, everything becomes simpler, and you can use a dynamic programming approach. The DP solution for the related one-dimensional k-means problem is described in this article , and the source code in R is available here . See the document for details, but the idea is essentially the same as that proposed by @SajalJain, and it can be easily adapted to solve the problem of k-medians, not k-means. For j <= k and m <= n, let D (j, m) denote the cost of the optimal solution of j-medians for x_1 ... x_m, where x_i is assumed in sorted order. We have recurrence

D(j,m) = min (D(j-1,q) + Cost(x_{q+1},...,x_m) 

where q varies from j-1 to m-1 and Cost is equal to the sum of the absolute distances from the median. With a naive implementation of O (n) Cost this would provide an O (n ^ 3k) DP solution for the entire problem. However, this can be improved to O (n ^ 2k) due to the fact that the cost can be updated in constant time, and not be calculated from scratch every time, using the fact that for an ordered sequence:

 Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_1...x_h)-x_1 if h is odd Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_2...x_h)-x_1 if h is even 

See the entry for more details. Except for the fact that updating the Cost function is different, the implementation will be the same for k-medians, as for k-means. http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf

Answer 2

As far as I understand, the problems are as follows:

we have n points on the line. we want to place k position on the line. I call them appointments. move each of n points in one of k directions so that the sum of the distances is minimal. I call this amount, total cost. Destinations may overlap.

The obvious fact is that for each point we must look for the nearest destinations on the left and the nearest destinations on the right and select the nearest.

Another important fact is that all destinations must be at points. because we can move them in a straight line to the right or left to reach a point without increasing the total distance.

Based on these facts, consider the following DP solution:

DP [i] [j] means the minimum total cost needed for the first point i, when we can use only j destinations and must place the destination at the i-th point.

to calculate DP [i] [j], fix the assignment to the i-th point (we have the choice of i), and for each choice (for example, the k-th point) calculate the distance needed for points between the i-th point and added New point (k-th point). add this with DP [k] [j - 1] and find the minimum for all k.

calculating the initial states (for example, j = 1), and the final answer remains in the form of an exercise!

Answer 3

Task 0 - sorting the position of objects in non-decreasing order

Define 'center' as the position of the object where it is shifted to.

Now we have two observations:

• For N positions the 'center' would be the position which is nearest to the mean of these N positions. For example, let 1,3,6,10 be positions. Then the average value = 5. The closest position is 6. Therefore, the center for these elements is 6. This gives us a position with a minimum displacement cost, when all the elements should be grouped into 1 group.

• Let N positions be grouped “optimally” into K-groups. When N+1 th object is added , then it will only bother the Kth group, i.e. first K-1 groups will remain unchanged.

From these observations, we build an approach to dynamic programming.

 Let Cost[i][k] and Center[i][k] be two 2D arrays. Cost[i][k] = minimum cost when first 'i' objects are partitioned into 'k' groups Center[i][k] stores the center of the 'i-th' object when Cost[i][k] is computed. 

Let {L} be the elements from iL,i-L+1,..i-1 which have the same center.
(Center[iL][k] = Center[i-L+1][k] = ... = Center[i-1][k])
These are the only objects that must be taken into account when calculating for the ith element (from observation 2)

Now

 Cost[i][k] will be min(Cost[i-1][k-1] , Cost[iL-1][k-1] + computecost(iL, i-L+1, ... ,i)) Update Center[iL ... i][k] 

computecost () can be found trivially by finding the center (from observation 1)

Time complexity:

 Sorting O(NlogN) Total Cost Computation Matrix = Total elements * Computecost = O(NK * N) Total = O(NlogN + N*NK) = O(N*NK) 

Answer 4

Let's look at k = 1.

For k = 1 and n odd, all points must move to the center point. For parity, k = 1 and n, all points must move to any of the central points or any spot between them. By "center" I mean the number of points in both directions, that is, the median.

You can see this because if you select the target spot, x, with a large number of points to the right of it, then the new target 1 to the right of x will lead to a decrease in cost (unless there is one more point to the right, and the left and target spots are point, in this case n is even, and the target is in / between the two center points).

If your points are already sorted, this is O (1) operation. If not, I believe that O (n) (through the order statistics algorithm).

Once you find that all points are moving, it is O (n) to find the value.

Thus, regardless of whether the points are sorted or not, it is O (n).