1
$\begingroup$

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

1 Answers 1

3

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.