# Permutation by interchange.

Start from $1, \ldots, n$, by interchanging the position of $i$ and $j$ where $i < j$ in each step, we are able to get any permutation of $\{1, \ldots, n\}$.

Do you think my conjecture is correct?

OK, it turns out this is very easy. What if we add the following extra constraint to the conjecture?

In each step we can only switch the position of $i$ and $j$ who are adjacent in current permutation.

-
Yes, your conjecture is correct. It is equivalent to the statement that the symmetric group $S_n$ is generated by transpositions. Or, to the simple observation that if you want to, say, reorder $n$-books in your shelf, you can do this by exchanging two books at a time (exchange the book currently in position $1$ with the book you want in position $1$; then the book currently in position $2$ with the one you want in position $2$; etc until you are left with just two books, either in order (you are done) or in the wrong place (exchange them). –  Arturo Magidin Mar 24 '12 at 22:32
Yes, and you should formulate it "from the end": Start from any permutation of $\left\lbrace 1,2,...,n\right\rbrace$. By interchanging the position of $i$ and $j$ where $i<j$ in each step, we are able to get the identity permutation. (Take your favorite sorting algorithm to prove this.) –  darij grinberg Mar 24 '12 at 22:33
@ArturoMagidin: not exactly equivalent, because he allows only the transpositions that increase the number of inversions. –  darij grinberg Mar 24 '12 at 22:33
«One can order a shelf of books using two hands, without even a place to temporarily put the books.» –  Mariano Suárez-Alvarez Mar 24 '12 at 23:03
The 2nd conjecture is that bubble sort works. And it does! –  Louis Mar 25 '12 at 0:03

Take $n$ people and stand them in a line. Tell each person "if the person on your right is taller than you, then swap places".
Each swap made takes a taller person on the right and a shorter person on the left. This seems to be where you were heading with the $i<j$ constraint, although, as it stands, it's an empty constraint: e.g. we can interchange the position of $4$ and $2$, since when $i=2$ and $j=4$, we have $i<j$.