7
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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:

  1. $X_i \le X_j \le Y_{\sigma(j)} \le Y_{\sigma(i)}$,
  2. $X_i \le Y_{\sigma(j)}\le X_j \le Y_{\sigma(i)}$, and
  3. $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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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