# Transforming Permutations

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:

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