Skip to main content
added 458 characters in body
Source Link

Given a permutation $\pi:[n]\to[n]$ of cards from $1$ to $n$ you can find the first card to move to the front the following way:

  1. $c \leftarrow n$
  2. for each $k$ from $n$ down to $1$ do
  3. $\space\space\space$ if $c = \pi(k)$ then
  4. $\space\space\space\space\space\space$ $c \leftarrow c - 1$
  5. $\space\space\space$ end if
  6. end for
  7. return $c$

In other words, choose the highest card, for which there is another card of higher value in front of it. More formally, choose a maximum $c\in[n]$ such that there exists a $c' > c$ with $\pi(k') = c'$, $\pi(k) = c$ and $k' < k$. Clearly, this card is not in order yet and since it is the one with the highest value it must be moved first if we want to keep the number of moves minimal. For the permutation $3,1,4,2$ this card is clearly card number $2$.

Given a permutation $\pi:[n]\to[n]$ of cards from $1$ to $n$ you can find the first card to move to the front the following way:

  1. $c \leftarrow n$
  2. for each $k$ from $n$ down to $1$ do
  3. $\space\space\space$ if $c = \pi(k)$ then
  4. $\space\space\space\space\space\space$ $c \leftarrow c - 1$
  5. $\space\space\space$ end if
  6. end for
  7. return $c$

Given a permutation $\pi:[n]\to[n]$ of cards from $1$ to $n$ you can find the first card to move to the front the following way:

  1. $c \leftarrow n$
  2. for each $k$ from $n$ down to $1$ do
  3. $\space\space\space$ if $c = \pi(k)$ then
  4. $\space\space\space\space\space\space$ $c \leftarrow c - 1$
  5. $\space\space\space$ end if
  6. end for
  7. return $c$

In other words, choose the highest card, for which there is another card of higher value in front of it. More formally, choose a maximum $c\in[n]$ such that there exists a $c' > c$ with $\pi(k') = c'$, $\pi(k) = c$ and $k' < k$. Clearly, this card is not in order yet and since it is the one with the highest value it must be moved first if we want to keep the number of moves minimal. For the permutation $3,1,4,2$ this card is clearly card number $2$.

Source Link

Given a permutation $\pi:[n]\to[n]$ of cards from $1$ to $n$ you can find the first card to move to the front the following way:

  1. $c \leftarrow n$
  2. for each $k$ from $n$ down to $1$ do
  3. $\space\space\space$ if $c = \pi(k)$ then
  4. $\space\space\space\space\space\space$ $c \leftarrow c - 1$
  5. $\space\space\space$ end if
  6. end for
  7. return $c$