Pergunta

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?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top