Ayuda con un mínimo de distancia de permutación problema

Question

Dado un ascendantly ordenado que no se número real negativo secuencia $X=x_1,...,x_n$, y otra que no sea de secuencia negativa $Y=y_1,...,y_n$, vamos a $P$ denotar todas las permutaciones de $Y$. Dado un determinado permutación $p\in P$, denotan la permutada $Y$ as $Y_p=y_{i_1},...,y_{i_n}$. Deje $p_0$ ser el particular permutación s.t. elemento $Y_{p_0}$ son ascendantly ordenado así.

Definir $d(X,Y_p)=|y_{i_1}-x_1|+...+|y_{i_n}-x_n|$, y deje $d^*=\min_{p\in P}{d(X,Y_p)}$. La pregunta es

Es $d^*=d(X,Y_{p_0})$, es decir, es la distancia mínima entre el $X,Y_p$ es la distancia entre la orden de $X$ y ordenó $Y$? Si no, se puede dar un contraejemplo?

Por ejemplo, supongamos que $X=1,2,3,4$, $Y=9,7,8,0$, a continuación,$d(X,Y_0)=d((1,2,3,4),(0,7,8,9))$. Parece que esta es la distancia mínima sobre todas las permutaciones de $Y$.

Gracias!

Answer 1

La respuesta es afirmativa. Supongamos por un momento que una permutación óptima de $Y$ no es ascendente, entonces existe al menos un par desordenada: $y_{i_j} > y_{i_k}$ ($j<k$). Por switchting este par, la diferencia en la distancia entre el $X$ e $Y_p$ se reduce: $$ \begin{align} &|y_{i_j}-x_j|+|y_{i_k}-x_k|-|y_{i_j}-x_k|-|y_{i_k}-x_j| \\ = \quad & (|y_{i_j}-x_j|-|y_{i_j}-x_k|)+(|y_{i_k}-x_k|-|y_{i_k}-x_j|) \\ \geq \quad & 0. \end{align} $$ Por lo tanto, hay siempre una óptima permutación de $Y$ que es ascendente. El óptimo no es necesariamente única. Esto es evidente cuando todos los elementos de $X$ son el mismo, o cuando todos los elementos de $Y$ son menores (o mayores) que todos los elementos de $X$. Incluso en otros casos, hay varios optima, como en tu ejemplo, usted puede tomar la permutación $(0,9,8,7)$.

Answer 2

Si usted tiene $x_1 < x_2$ e $y_1 < y_2$ hay tres casos:

• $x_1 < x_2 < y_1 < y_2$
• $x_1 < y_1 < x_2 < y_2$
• $y_1 < x_1 < x_2 < y_2$

Usted puede comprobar fácilmente en todos los casos que $|y_1 - x_1| + |y_2 - x_2| \leq |y_1 - x_2| + |y_2 - x_1|$.

Quiere mostrar: para cualquier $\sigma \in S_n$,

$$\sum_{k=1}^n |x_k - y_k| \leq \sum_{k=1}^n |x_k - y_{\sigma(k)}|$$

Vamos a proceder por inducción en $n$. El argumento anterior sirve como una base de caso.

Ahora, considere la posibilidad de cualquier $\sigma \in S_{n+1}$. Si $\sigma$ tiene un punto fijo, a continuación, $\sigma(j) = j$ para algunos $j$ y el plazo $|x_j - y_j|$ aparece en ambas sumas. Entonces podemos restar este término y así tenemos que reducir el problema a uno de una permutación en $n$ letras. Por la hipótesis de inducción, hemos terminado.

Supongamos $\sigma$ no tiene puntos fijos. Deje $\sigma(n+1) = m$ e $\sigma(k) = n+1$.

Considerar qué pasaría con las sumas que si "intercambia" estos dos. Deje $\sigma'$ ser $\sigma$ con $\sigma'(n+1) = n+1$ e $\sigma'(k) = m$. Desde $x_k < x_{n+1}$ e $y_m < y_{n+1}$, sabemos que

$$|x_k - y_m| + |x_{n+1} - y_{n+1}| \leq |x_{k} - y_{n+1}| + |x_{n+1} - y_m|$$

Desde $\sigma$ e $\sigma'$ está de acuerdo en todas las demás posiciones, esta muestra

$$ \sum_{k=1}^n |x_k - y_{\sigma'(k)}| \leq \sum_{k=1}^n |x_k - y_{\sigma(k)}|$$

Y por lo tanto esto reduce al caso con un punto fijo.

Hecho.