Isn't the quickest way to determine whether a series of number is even permutation or not by the check length of it to see if it's even or not?

Question

So, to my understanding of even or odd permutation, I reckon that we can just check the length of the transposition of a series of numbers, to see if it's even or odd to determine if it's even or odd permutation.

Then, with that logic, I'm ok with this [5, 4, 2, 7, 6, 0, 8, 9, 3, 1] list of number(length: 10) is not even permutation,

but saying this [4, 3, 1, 0, 6, 2, 8, 7, 5](length: 9) is not a even permutation just drives me insane!!! What's wrong???

A little more background: I am writing a program to return if the input list of number is even permutation or not, and with my previous logic stated, my program is pretty simple:

def is_even(p):
    return len(p) % 2 != 0

so the program simply return the result of checking length of numbers by getting the remainder to see if it's odd or even.

But the program pass this [5, 4, 2, 7, 6, 0, 8, 9, 3, 1](length:10) is not a even permutation as well as this [4, 3, 1, 0, 6, 2, 8, 7, 5](length:9)

Could someone tell me the testing system is wrong? thank you... or maybe me? but how? It was not how even permutation to be determined??

Answer 1

Let us consider the example you give of permutation $p$ :

$$(4, 3, 1, 0, 6, 2, 8, 7, 5), \ \text{meaning that} \ 0 \mapsto 4, 1 \mapsto 3, 2 \mapsto 1, 3 \mapsto 0, 4 \mapsto 6,...$$

Here is an ill-known graphical trick : count the number of intersections in this diagram

(which is the number of "inversions") As there are $13$ (an odd number) of them, permutation $p$ is odd...

Answer 2

I suppose $[4, 3, 1, 0, 6, 2, 8, 7, 5]$ stands for the permutation that maps $0\mapsto 4$, $1\mapsto 3$, $2\mapsto 1$, $3\mapsto 0$, etc. Then this permutation splits intop the following cycles: $$0\mapsto 4\mapsto 6\mapsto 8\mapsto 5\mapsto 2\mapsto 1\mapsto 3\mapsto 0 $$ and $$7\mapsto 7. $$ Such a cycle with $k$ arrows is even iff $k$ is odd (indeed, the simplest odd permutation is a single transposition $x\mapsto y\mapsto x$ with its two arrows). The pemutation as a whole isodd iff this splitting into cycles gives us an odd number of odd cycles. So $[4, 3, 1, 0, 6, 2, 8, 7, 5]$ consists of one odd and an even cycle (and perhaps additional implicit even cycles such as $42\mapsto 42$) and is odd. You simply cannot tell this from the length of the original array.