Transforming one list of numbers into another by a sequence of "moves" Given two unordered lists of integers, both of length $n$, named $X$ and $Y$, how would one find the minimum number of moves required to transform the elements of $X$ into the elements of $Y$ ? 
Ordering doesn't matter in the sense that the modified version of $X$ has to be a permutation of $Y$.

A move consists of picking elements from the $X$ list at indexes $i,j$ where $i \neq j$ and incrementing $x_j$ by $1$ while decrementing $x_i$ by $1$.

I've checked out a similar problem that was meant to find a minimal number of moves done in order to equalize an array, but that doesn't feel helpful here.
Any ideas?
 A: Order the lists in decreasing order,
$$
X = [x_1, x_2, \ldots, x_n] \; ; Y = [y_1, y_2, \ldots, y_n]
$$
where $x_i \ge x_2 \ge \cdots \ge y_n$ and $y_1 \ge y_2 \ge \cdots \ge y_n$.
Then:


*

*If $\sum_i x_i \ne \sum_i y_i$, transforming one into the other is impossible, as each move does not change the sum of the list.

*Otherwise, the minimum number of moves is given by
$$
\frac12 \sum_{i=1}^n |x_i - y_i|. \tag{1}
$$
Proof: Firstly, to achieve this minimum, find an element $x_i$ such that $x_i > y_i$ and one such that $x_j < y_j$. (Assuming the lists are not yet equal, they differ at some index; then if $X$ is bigger at that index, $X$ must be smaller at some other index to compensate since the sums are equal.) Perform a move on $x_i, x_j$. Then the sum of the differences decreases by $2$, so the quantity in (1) decreases by $1$. Then repeat this until list $X$ equals list $Y$.
In the course of the above algorithm, the list $X$ may fail to be in decreasing order sometime in the middle (depending on how we do the moves), but it doesn't matter, the algorithm still shows the minimum in (1) is achieved.
Next, we want to show (1) is a theoretical minimum (this is the part that will make use of $X,Y$ being in decreasing order).
Consider any sequence of $k$ moves starting with $X$ and arriving at some reordering of $Y$.
(During the course of these moves, again $X$ may not always be in decreasing order.)
Denote the reordering of $Y$ by $[y_{\sigma(1)}, y_{\sigma(2)}, y_{\sigma(3)}, \ldots, y_{\sigma(n)}]$, where $\sigma$ is a permutation of $1$ through $n$.
Note that each move will only decrease the quantity $\tfrac12 \sum_{i = 1}^n |x_i - y_{\sigma(i)}|$ by at most one, because it will only change two terms and each either goes up by one or down by one. After all $k$ moves, we have that
the quantity $\tfrac12 \sum_{i=1}^n |x_i - y_{\sigma(i)}|$ is $0$. It follows that the original list $x_i$ satisfies
$$
k \ge \sum_{i=1}^n |x_i - y_{\sigma(i)}|.
$$
To complete the proof, we would like to show that
$$
\sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|
$$
implying that using the strictly decreasing order is optimal, and the number of moves $k$ is bounded below by the quantity in (1).
This last inequality is proven here.
A: This is equivalent to computing the Earth mover's distance of the histograms corresponding to the two lists.
