So you have a permutation $f: X \to X$ for which you can efficiently compute $f(x)$ from $x$.
I think a good way to do any of the things you mentioned is to make a checklist for the elements of $X$.
Then you can start with the first unchecked element and follow the chain $x, f(x), f(f(x))$, etc. checking off each element as you find it until you reach
an element that is already checked. You have now traversed one cycle.
Then you can pick the next unchecked element and traverse that cycle, and so
on until all elements are checked.
While you traverse a cycle you can easily
- Count the cycle length
- Record the cycle, or
- Record transpositions
All this works in roughly linear time. Obviously just counting the cycle lengths
is going to be the fastest.
Let $\pi=\langle p_1,p_2,\ldots,p_n\rangle$ be a permutation of $[n]=\{1,\ldots,n\}$. If $\pi$ has no inversions, it’s the identity permutation, which is even, so assume that $\pi$ has at least one inversion. Suppose that $1\le j<k\le n$, and $p_j>p_k$. Let $\rho=(p_j,p_k)\pi$ (where I apply the transposition first and then $\pi$); if $\rho=\langle r_1,\ldots,r_n\rangle$, then $r_j=p_k$, $r_k=p_j$, and $r_i=p_i$ if $i\in[n]\setminus\{j,k\}$. This swap obviously gets rid of the $\langle j,k\rangle$ inversion.
The only other inversions affected by this swap are those that involve position $j$ or $k$ and a position between $j$ and $k$. Suppose that $j<i<k$ and $\langle j,i\rangle$ is an inversion in $\pi$, i.e., $p_j>p_i$. Either $p_k>p_i$, in which case $\langle j,i\rangle$ is still an inversion in $\rho$, or $p_i>p_k$, in which case the swap gets rid of a $\langle j,i\rangle$ and an $\langle i,k\rangle$ inversion. Similarly, if the swap gets rid of an $\langle i,k\rangle$ inversion (instead of replacing it with a new one), it also gets rid of a $\langle j,i\rangle$ inversion. In all cases the number of inversions other than $\langle j,k\rangle$ that are affected by the swap is even. Thus, the total number of inversions affected by the swap is odd. Note also that the number of inversions is reduced by at least one.
Can you see how to finish it from here? I’ve left the conclusion of the argument in the spoiler-protected block below.
Start with any non-identity permutation $\pi$. Repeatedly multiply by transpositions to remove inversions until no inversions remain. Say you multiplied by $m$ transpositions. Then $\pi$ has the same parity as $m$, and since each multiplication by a transposition removed an odd number of inversions, the number of inversions also has the same parity as $m$.
Best Answer
Let's define $\varphi : \sigma \mapsto \displaystyle\prod_{1\leq i < j \leq n} \dfrac{\sigma(j)-\sigma(i)}{j-i}$.
We prove that $\varphi(\sigma \circ \tau)=\varphi(\sigma) \varphi(\tau)$. Indeed, \begin{align*} \varphi(\sigma \circ \tau) & = \prod_{1\leq i < j \leq n} \dfrac{\sigma \circ \tau(j)-\sigma\circ \tau(i)}{j-i}\\& = \prod_{1\leq i < j \leq n} \dfrac{\sigma \circ \tau(j)-\sigma\circ \tau(i)}{\tau(j)-\tau(i)} \times \dfrac{\tau(j)-\tau(i)}{j-i}\\& = \prod_{1\leq i < j \leq n} \dfrac{\sigma \circ \tau(j)-\sigma\circ \tau(i)}{\tau(j)-\tau(i)} \times \prod_{1\leq i < j \leq n}\dfrac{\tau(j)-\tau(i)}{j-i}\\& = \prod_{1\leq i < j \leq n} \dfrac{\sigma (j)-\sigma(i)}{j-i} \times \prod_{1\leq i < j \leq n}\dfrac{\tau(j)-\tau(i)}{j-i}\\&=\varphi(\sigma)\varphi(\tau) \end{align*}
We prove that if $\tau$ is a transposition, then $\varphi(\tau)=-1$. Indeed, if $\tau$ is the $(i,j)$ transposition, then $$\varphi(\tau)= -\prod_{k \neq i,j}\dfrac{\tau(k)-\tau(i)}{k-i}\dfrac{\tau(k)-\tau(j)}{k-j} =-\prod_{k \neq i,j}\dfrac{k-j}{k-i}\dfrac{k-i}{k-j} = -1 $$
The result directly follows from the two points above.