0
$\begingroup$

Sorry for this basic question. In here, we have $2$ inversions of $1$ element (from the set $\lbrace 1,2,3\rbrace$):

$$ 132, \\ 213, $$

and that $321$ is a $3$-element inversion permutation. Why $321$ is not a 1-element inversion (just switch $1 \rightarrow3$?

$\endgroup$
  • 1
    $\begingroup$ We refer to inversions as the operation of swapping adjacent elements in the permutation. Since $1$ and $3$ are not adjacent in the beginning, it is not accomplishable via a single inversion. $\endgroup$ – JMoravitz May 19 '16 at 17:24
  • $\begingroup$ I think I get it more or less. Certainly the adjacent word helps a lot! Just a comment, by some strange reason, all the definitions that I have seen never say it. $\endgroup$ – user2820579 May 19 '16 at 17:28
1
$\begingroup$

First of all the number of inversions isn't defined as the minimum number of switches we can do to arrange a permutation. As explicitly stated in the give link: "Given a permutation $a_1, a_2, a_3,...$, an of the $n$ integers $1, 2, 3, ..., n$, an inversion is a pair $(a_i, a_j)$ where $i < j$ and $a_i > a_j$".

Another way to look on inversions is as swapping two adjacent elements, s.t $(a_i, a_{i+1})$ where $a_i > a_{i+1}$. So the number of inversions in a sequence is given by the number of such defined swaps you need to perform in order to sort the sequence. Additionally this type of swapping is called Bubble Sort

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.