Rearranging to reach original order of cards

Valery123

New member
Joined
Feb 18, 2019
Messages
1
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...
 
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.
 
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
 
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
 
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.
 
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.)
 
Top