Algorithm to match numbers with minimum number of moves

Question

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?

Answer 1

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

Answer 2

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$.

Answer 3

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.