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??
Best Answer
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...