John has a set of cards laid on a table in this order:
A, B, C, D, E, F
His friend shuffles the order of the cards randomly, which results in this order:
D, F, B, C, A, E
If John is allowed to swap only 2 adjacent cards at a time, what is the smallest number of swaps to reach the original order of cards?
Show your solution swap by swap.
I got 9 swaps to be the least, but this was by swapping cards which would both be closer to their original positions after the swap:
D F B C A E - Swap F and B
D B F C A E - Swap F and C
D B C F A E - Swap A and F
D B C A F E - Swap F and E
D B C A E F - Swap C and A
D B A C E F - Swap B and A
D A B C E F - Swap A and D
A D B C E F - Swap D and B
A B D C E F - Swap D and C
A B C D E F
This method seems take a while - is there a better method?
There are multiple ways of reaching this as well with the same number of swaps...
A, B, C, D, E, F
His friend shuffles the order of the cards randomly, which results in this order:
D, F, B, C, A, E
If John is allowed to swap only 2 adjacent cards at a time, what is the smallest number of swaps to reach the original order of cards?
Show your solution swap by swap.
I got 9 swaps to be the least, but this was by swapping cards which would both be closer to their original positions after the swap:
D F B C A E - Swap F and B
D B F C A E - Swap F and C
D B C F A E - Swap A and F
D B C A F E - Swap F and E
D B C A E F - Swap C and A
D B A C E F - Swap B and A
D A B C E F - Swap A and D
A D B C E F - Swap D and B
A B D C E F - Swap D and C
A B C D E F
This method seems take a while - is there a better method?
There are multiple ways of reaching this as well with the same number of swaps...