[Solved]: Sort deck of cards with least no of moves

Problem Detail: 

We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

4 3 1 2  3 4 1 2 2 3 4 1 1 2 3 4 

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

2 3 1 4  1 2 3 4 

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2

Asked By : HimalayanCoder

Answered By : Dennis Kraft

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45569