0

Assume I want to change [1,2,...,n] to anthor order, say [n,n-1,...,2,1].

In the exmaple, I know I can do like this

[1,2,...,n] $\rightarrow$ [2,1...,n]$\rightarrow$ [2,3,1,...,n]$\rightarrow \cdots \rightarrow$ [2,...,n,1]

$\rightarrow$ [3,...,n,2,1]$\rightarrow \cdots$ $\rightarrow$ [n,n-1,...,2,1],

so I need to swap adjacent elements $\frac{(0+n-1)n}{2}$ times.

The above process depends on my observation, but if the aim order of the numbers is more complicated, it won't be this easy to know by observation.

I wonder if there is any genral method to know that if the permutation is even or odd?

RicknJerry
  • 101
  • What is a "permutation" in this context? A swap? Adjacent elements only? – Parcly Taxel Apr 25 '20 at 10:51
  • 1
    It's not clear how you're using the term "permutation". In standard usage, this term refers to a bijection on a set. You seem to be referring to only particular types of such operations, but it's not clear from your example which these are. In particular, they are apparently neither all cyclical permutations (since you reverse the order of $1$ and $2$ in the middle step), nor all transpositions (since you're shifting almost all elements in each of the steps). – joriki Apr 25 '20 at 10:52
  • There is only one permutation necessary, as the permutations form a group. You are asking for the minimal number of transpositions which are necessary. IIRC the symmetric group can be generated by (12) and (12...n), which may lead to a recursive approach to answer the word problem in the symmetric group. Note that a generic answer, i.e. how many steps are necessary in general, can differ a lot from specific examples, or even the presentation of your question. I could imagine that a lower bound could be less if the input permutation is already given as a product of disjoint cycles. – Marius S.L. Apr 25 '20 at 10:53
  • @ParclyTaxel Yes, that’s what I mean! – RicknJerry Apr 25 '20 at 10:55
  • I edited the question. – RicknJerry Apr 25 '20 at 10:55
  • I am a little uncertain which swaps you mean. You mention adjacent elements, but you seem to be swapping non-adjacent elements in the example. If you do mean adjacent, then the answer is given by counting so-called inversions. – Tobias Kildetoft Apr 25 '20 at 11:10
  • @RicknJerry At the end of your question you ask if there is a method to know if the permutation is even or odd. Do you just want to know if the number of transpositions required is even or odd, or do you actually want to know the minimum number of transpositions required? – Ragib Zaman Apr 25 '20 at 11:19
  • @RagibZaman maybe both! Although in most cases encountered, I only need to know the former. – RicknJerry Apr 25 '20 at 11:22

0 Answers0