# Rearranging to reach original order of cards

#### Valery123

##### New member
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...

#### tkhunny

##### Moderator
Staff member
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...
Bubble Sort. Not a pretty sight.

#### Harry_the_cat

##### Senior Member
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...
What if you just swap them into their original positions:
D F B C A E
A F B C D E - swapped A and D (to get A in position 1)
A B F C D E - swapped B and F (to get B in position 2)
etc
6 swaps in all

#### Jomo

##### Elite Member
What if you just swap them into their original positions:
D F B C A E
A F B C D E - swapped A and D (to get A in position 1)
A B F C D E - swapped B and F (to get B in position 2)
etc
6 swaps in all
Wouldn't that be 5 swaps? Also they are not adjacent swaps as the OP stated

#### Dr.Peterson

##### Elite Member
It's clear that we need at least 7 swaps, since if you add up the distance each letter has to move, we get 14, and each swap moves two letters a distance of 1 each.

I got 9 swaps myself, and that looks minimal, because a couple letters are forced to move in the wrong direction for the sake of others. In fact, the last and most carefully thought out of my four 9-swap solutions is identical to yours.

Do you know any math that might be relevant, beyond just experimenting? I'm satisfied with my work, though it isn't an absolute proof.

#### Harry_the_cat

##### Senior Member
Oopsie!! That's what happens when you don't read the question carefully! (And yes Jomo, it would be only five if it was allowed.)