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

tkhunny

Moderator
Staff member
Joined
Apr 12, 2005
Messages
9,790
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

Full Member
Joined
Mar 16, 2016
Messages
943
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
Joined
Dec 30, 2014
Messages
3,045
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
Joined
Nov 12, 2017
Messages
3,078
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

Full Member
Joined
Mar 16, 2016
Messages
943
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