I have two vectors, $X$ and $Y$ of equal length $n$. Basically, I want to match up each value from $X$ with a value from $Y$, so that the sum of the differences between the two values per pair is as small as possible. So in essence, I suppose I want to minimize the following quantity by rearanging the elements of $X$ and $Y$: $$ \sum\limits_{i=1}^n\left| X_i - Y_i\right| $$ To solve this I could go through every possible combination, compute the quantity and find the minimum. However, for even moderately long vectors the number of combinations is huge. I feel like there is probably a much easier way to solve this, or that it is probably equivalent to (or very similar to) a proper statistical thing, although I am not sure what that would be called and consequently I haven't been able to find it yet.
1 Answer
Sort the two vectors and match them in order.
The question seeks a permutation $\sigma$ of the indexes $\{1,2,\ldots, n\}$ that minimizes
$$f_{X,Y}(\sigma) = \sum_{i=1}^n |X_i - Y_{\sigma(i)}|.$$
Let $X_{[1]} \le X_{[2]} \le \cdots \le X_{[n]}$ be the order statistics for $X$. Use similar notation for the order statistics of $Y$. Then a permutation guaranteed to minimize $f_{X,Y}(\sigma)$ is the one that matches $X_{[i]}$ to $Y_{[i]}$ for each $i$.
To see this, suppose that $X_i \le X_j$ but $Y_{\sigma(i)} \ge Y_{\sigma(j)}$. There are only six ways in which these four numbers can be ordered. Three of them are the following:
- $X_i \le X_j \le Y_{\sigma(j)} \le Y_{\sigma(i)}$,
- $X_i \le Y_{\sigma(j)}\le X_j \le Y_{\sigma(i)}$, and
- $X_i \le Y_{\sigma(j))}\le Y_{\sigma(i)}\le X_j$.
Changing $\sigma$ to match $i$ with $\sigma(j)$ and $j$ with $\sigma(i)$ decreases $f_{X,Y}(\sigma)$ by $0$, $2|X_j - Y_{\sigma(j)}|$, and $2|Y_{\sigma(i)}-Y_{\sigma(j)}|$, respectively.
The other three cases are similar to these (but with the $Y_{*}$ in the positions of the $X_{*}$), with similar results upon changing $\sigma$. In no case does $f$ increase. Therefore, if $\sigma$ does not match up the ordered sequences of the $X$ and $Y$, we can always replace it with one that does match them up and achieves no worse a value of $f$, QED.
Because sorting can be accomplished (in the usual models of computing) with $O(n\log(n))$ effort, such a solution can be found in $O(n\log(n))$ time by sorting both the $X_i$ and $Y_i$.