Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a simple combinatorial proof that for any two distinct permutations of a set you can transform one into the other by performing a series of exchanges of 2 objects at a time?

ie. ABCD$\rightarrow$BDAC:

ABCD/CBAD/BCAD/BDAC

share|improve this question
7  
If you want a constructive method, bubble sort gives you an (not the most efficient) algorithm. –  Willie Wong Aug 12 '11 at 2:53
    
By cycle decomposition it suffices to show that cyclic permutations have this property, and this is straightforward by induction. –  Qiaochu Yuan Aug 12 '11 at 3:04
1  
Thank you for your answers. Is it permissible to reason by induction: Demonstrate the cases with 1,2, and 3 items, then claim that to perform the transformation with an additional item one can simply perform the exchanges on the original items ending with the item that needs to by exchanged into the last position in the place that the new item needs to be exchanged into? –  user12998 Aug 12 '11 at 3:30
    
It is not clear what you mean by a 'combinatorial' proof. To change any permutation to ABCD... you can perform transpositions (exchanges of two objects at a time) first to put A in the first place, then keeping A fixed, make an exchange to put B in the second place etc. You can even do this by exchanging adjacent elements to bring A to the front. It should be obvious that if you get to ABCD... from any permutation then by reversing the process you can get to any permutation. The point is to be systematic. –  Mark Bennet Aug 12 '11 at 4:42
1  
If you are thinking about building cycles from transpositions you might want to explore the cycles you get from (1 2); (1 2)(1 3); (1 2)(1 3)(1 4) etc (where it is intended that you do the leftmost transposition first). –  Mark Bennet Aug 12 '11 at 4:45
show 2 more comments

1 Answer

up vote 3 down vote accepted

Synthesis of answers given in the comments:

The construction of any sorting algoritm is sufficient to demonstrate the principle, every permutation can be arranged one step at a time into a "sorted" list thus it can be rearranged into any other permutation. Similarly, you can simply exchange the items in order by using your first (second, third...) exchange to place whichever object is first (second, third...) into the appropriate place in the second permutation and skipping objects that don't move. Thirdly, the entire principle can be demonstrated by induction on cyclic permutations of each order, which is non-constructive but justifies the process.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.