0
$\begingroup$

I have two ordered lists, $l_1$ and $l_2$, each containing $N$ elements ${e_1, e_2, ..., e_N }$ (each only once) in some order.

For each of these elements I calculate their absolute index difference between those two lists and sum them up.

Example with $ N=3 $:

$ l_1 = [e_1, e_2, e_3] $

$ l_2 = [e_2, e_3, e_1] $

$ d_{e_1} = abs(l_1.index(e1) - l_2.index(e1)) = abs(1 - 3) = 2$

$ d_{e_2} = abs(l_1.index(e2) - l_2.index(e2)) = abs(2 - 1) = 1$

$ d_{e_3} = abs(l_1.index(e3) - l_2.index(e3)) = abs(3 - 2) = 1$

$ result = d_{e_1} + d_{e_2} + d_{e_3} = 2 + 1 + 1 = 4 $

What is the maximum possible sum of differences for $N$ elements?

If the two lists have their elements in the same order the sum of differences is the minimum, 0.

The distributions look like this:

enter image description here

enter image description here

It may be that the answer is $ \lfloor N^2/2 \rfloor $, achieved by letting $l_2$ have the reverse order of $l_1$, so there would only be one permutation which has the maximum difference, but I'm not certain

$\endgroup$
6
  • $\begingroup$ When you say $e_1, \ldots, e_N$ do you mean $1, \ldots, N$? Otherwise hard to bound the difference, consider $1, N, N^2, \ldots, N^N$ as your list in straight and reverse order... $\endgroup$
    – gt6989b
    Commented Jul 28, 2023 at 14:03
  • $\begingroup$ Yes, the integers work $\endgroup$
    – 2080
    Commented Jul 28, 2023 at 14:10
  • 1
    $\begingroup$ @gt6989b The elements' values do not matter; OP is taking the difference of each element's positions in the two permutations. $\endgroup$
    – angryavian
    Commented Jul 28, 2023 at 16:01
  • 1
    $\begingroup$ @angryavian missed that; in that case, just taking a rearranged order of integers $1,\ldots,N$ is sufficient. It is intuitively obvious that the greedy solution produces the optimal answer. I tried this in Excel for a couple and this answer can be duplicated but cannot be beat. The max sum abs-diffs I found for $N=1,2,3,4,5$ are $0,2,4,8,12$ $\endgroup$
    – gt6989b
    Commented Jul 28, 2023 at 16:15
  • $\begingroup$ @angryavian Aye, it seems to be this OEIS sequence: oeis.org/… $\endgroup$
    – 2080
    Commented Jul 28, 2023 at 16:33

1 Answer 1

1
$\begingroup$

We can without loss of generality assume one of the permutations is $l_1 = [e_1, \ldots, e_N]$, and explore options for the second permutation $l_2$.

Your hypothesis is that the reverse ordering $l_2 = [e_N, \ldots, e_1]$ produces the largest distance, which is $$2(1+3+\cdots+(N-1)) = 2(N/2)^2 = N^2/2$$ for even $N$, and $$2(2+4+\cdots+(N-1))=(N-1)(N+1)/2=\frac{N^2}{2} - \frac{1}{2}$$ for odd $N$. Or, as you said yourself, $\lfloor N^2/2\rfloor$.


Claim: given a permutation $l_2 = [e_{i_1}, \ldots, e_{i_N}]$, if there is a pair $i_j < i_k$ for some $j < k$, swapping them will produce a greater difference from $l_1$.

Proof: the two elements $e_{i_j}$ and $e_{i_k}$ contribute $$|i_j-j| + |i_k-k|$$ to the formula for the difference between $l_2$ and $l_1$. If we swap the two elements, they instead contribute $$|i_j - k| + |i_k - j|.$$ Using the inequalities $i_j < i_k$ and $j<k$, you can show with some casework that $$|i_j-j| + |i_k-k| \le |i_j - k| + |i_k - j|,$$ so making this swap will either increase the difference or keep it the same.

Using the claim to prove that $\lfloor N^2/2\rfloor$ is the maximum difference. Suppose $l_2 = [e_{i_1}, \ldots, e_{i_N}]$ has the maximum difference with $l_1$. If $l_2 = [e_N, \ldots, e_1]$ then we are finished. Otherwise, there exists some pair $i_j < i_k$ where $j < k$. Because $l_2$ has the maximum distance, this swap cannot increase the difference with $l_1$, so it will keep the difference with $l_1$ the same. We can repeat this argument with the new permutation. Eventually after many swaps we will go through a sequence of permutations all while maintaining the same difference with $l_1$, and end up with $[e_N, \ldots, e_1]$, which implies that the original permutation had difference $\lfloor N^2/2\rfloor$ with $l_1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .