Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far.


Given a series of numbers, e.g.

[3, 1, 1, 1]

How would one most efficiently turn all of the numbers into the same number, with the minimum number of "moves"? By "move" is meant adding or removing one from a number.

In the above example, the most efficient moves would be:

[1, 1, 1, 1]

This would require 2 moves, reducing the first number twice.

I can't figure out the best way to find this out, given much larger arrays of hundreds of numbers.

I originally tried computing the rounded average number (sum of all divided by length), and then reducing them to the computed average, but the above example broke this, requiring 4 moves instead of 2.

I suppose I could figure:

  1. The average,
  2. The mode,
  3. The median

and get the edit distance of each of them, choosing the minimum distance. However, I am not sure that this would be correct in every single instance. How can I know?

share|improve this question
    
If domain is limited you can try all possibilities from min to max. Otherwise you may try to use mode or median. –  bartek May 6 at 21:45
    
Thanks @Bartek. Seems like trying all possibilities would be tremendously inefficient if dealing with hundreds or thousands of numbers. I'll check out mode/median. But are these certain to produce results in every instance? That's my main question. I am looking for a certain, efficient algorithm. –  dc2 May 6 at 21:48
    
Does the number have to be in the set of numbers, or can it be any integer? –  TCSGrad May 6 at 22:05
    
@TCSGrad It can be any integer, but obviously you would want to pick one that is in between the min and max number. In this case, either 1, 2, or 3. –  dc2 May 6 at 22:29

3 Answers 3

up vote 10 down vote accepted

The answer is to take the median. One of the properties of the median is that it minimizes the L1 distance to each element. (To make sense of the Wikipedia article, take the probability distribution to be the uniform distribution over your original series of numbers).

This is the algorithm which solves the problem (originally written by dc2):

function median(arr) {
  arr.sort(function(a, b) { return a - b; });
  var half = floor(arr.length/2);
  if ( arr.length % 2 ) {
    return arr[half];
  } else {
    return (arr[half-1] + arr[half]) / 2.0;
  }
}

function minl1(arr) {
  var moves = 0;
  var mdn = median(arr);
  for ( var i = 0; i < arr.length; ++i ) {
    moves += Math.abs(mdn - arr[i]);
  }
  return moves;
}

minl1([3, 1, 1, 1]); // -> 2
share|improve this answer
    
Yeah, that did it. Funny how that works. Doesn't seem like the median would do it, but hey. Thanks a lot. –  dc2 May 7 at 3:15
1  
See my answer for a proof. –  Yuval Filmus May 7 at 3:54
    
@dc2: You can't "make sure" by "trying it out". –  Raphael May 7 at 7:48
1  
Just to note: you can calculate median O(n) time –  bartek May 7 at 7:53
1  
@Raphael Is it okay to include OP's code in some other answer, with no reference to OP? –  thefourtheye May 7 at 8:33

As TCSGrad mentions, given a list of integers $x_1,\ldots,x_n$, you're looking for the integer $m$ minimizing $$ \delta(m) = \sum_{i=1}^n |m - x_i|. $$ It is instructive to compute $\delta(m+1) - \delta(m)$: $$ \delta(m+1) - \delta(m) = \sum_{i=1}^n \begin{cases} +1 & m \geq x_i \\ -1 & m < x_i \end{cases} = \#\{i : m \geq x_i\} - \#\{i : m < x_i\}.$$ As $m$ goes from $-\infty$ to $+\infty$, the quantity $\delta(m+1) - \delta(m)$ goes from $-n$ to $n$. Moreover, it switches values only at the points $x_1,\ldots,x_n$. It is not hard to check that an optimal value of $m$ is the minimal point at which $\delta(m+1) - \delta(m) \geq 0$. This minimal point is one of the $x_i$, so the editing distance is $\min(\delta(x_1),\ldots,\delta(x_n))$.

Suppose further that all $x_i$ are distinct and that $n$ is odd. Let $m$ be the median of the $x_i$. Then $\delta(m+1) - \delta(m) = 1$ while $\delta(m) - \delta(m-1) = -1$, and so $m$ is the unique optimum. If $n$ is even then a similar calculation shows that we can choose any point in the interval connecting the medians. Similar but more elaborate reasoning shows that any median is optimal even when the $x_i$ are not distinct. So there is actually no need to calculate $\delta$ on all $x_i$.

share|improve this answer
    
You might have missed it, but this answer (almost) proves that the median is the optimal choice. –  Yuval Filmus May 7 at 4:14
1  
your answer was excellent and I upvoted it. Unfortunately for me, a little too excellent as I am not that well versed in scientific notation, leaving most of it as rendered garble. That's my problem, not yours. –  dc2 May 7 at 5:17

The problem can be formulated as a LP problem:

Given a set of $n$ numbers $[a_1,a_2... a_n]$, solve the following LP:

$$ \min \sum |a_i - x| $$

(Removed constraints on $x$, which weren't necessary as Raphael pointed out)

Once the LP is solved, you'll get a value of $x$ corresponding to the solution. If $x$ is an integer, you are done - else, round it to the nearest integer.

EDIT: As pointed out in the comments, the objective function should be sum over absolute differences. In order to transform it back to a standard LP, we can rewrite the LP as:

$$ \min \sum a'_i $$

subject to:

$$ a'_i \geq a_i - x\ \forall i $$ $$ a'_i \leq a_i - x\ \forall i $$ $$ a'_i, x' \geq 0\ \forall i $$

At the optimal solution, $a_i' = | a_i - x|\ \forall i$, and we can get the value of $x$ from the solution.

share|improve this answer
    
So if I understand this correctly, in my example, x would be 1 - 3, and so I would find the edit distance of 1, 2 and 3, and then do a min on that? –  dc2 May 6 at 22:45
    
@dc2: This would minimize the sum of the distances between each number and $x$, where $x$ is the convergent number. The constraints ensure the LP terminates quickly, and does not search over all integers! –  TCSGrad May 6 at 22:46
    
Why are the constraints necessary? –  Raphael May 6 at 23:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.