2
$\begingroup$

In the scope of my scheduling research, the question has been raised on whether distance-preserving permutations can be constructed easily.

Suppose that our domain is the set of natural numbers up until $n$, that is: $D=\{1,2,...,n\}$ where $n\geq 1$.

A permutation $\pi$ is a distance-preserving permutation in my context is one that has the following property: $|\pi(i) - \pi(j)| = |i-j|$.

For example, the most trivial distance-preserving permutation I have come up with is the following: $\pi(i) = n-i+1$, which is the permutation that maps $1$ to $n$, $2$ to $n-1$, etc. It can be easily shown that $|\pi(i) - \pi(j)| = |i-j|$.

My intuition says that there are no more distance-preserving permutations, since if we draw this as a graph where the $x$-axis is the numbers in $D$ and the $y$-axis is the values $\pi(i)$ then we will have a $90$-degree cornered triangle with the corner facing north-east, its' equal edges being the distances $|i-j|$ and $|\pi(i) - \pi(j)|$.

Are there distance-preserving permutations other than the above trivial one?

$\endgroup$
8
$\begingroup$

The only permutations who satisfy this condition are the identity and its inverse (as string inverse), $\pi(i)=n-i+1$.

Note that $1$ has to be in one of the edges (if it has two neighbors, then at least one of them is bigger than $2$ and the condition is not satisfied). Placing $1$ in the left edge forces the entire permutation to be the identity, and placing $1$ in the right edge forces the permutation to be its inverse.

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