1
$\begingroup$

I made a conjecture today

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.

  • 1
    The 2nd conjecture is that bubble sort works. And it does!2012-03-25

1 Answers 1

1

The easiest way to interpret this problem is as a sorting algorithm.

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

We eventually will get the tallest person on the left. Then, by induction (ignoring the tallest person), we will get the next-tallest person on his right, and so on, down to the shortest person on the right.

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

Reversing this process shows that we can reach any permutation via transpositions.