Recognizing even or odd permutation easily?

[vulpe]

Hello folks, I'm not even sure if this is the place to put this but with some luck it might be.

I just have a general question about permutations. I understand the concept of even and odd permutations of a set of numbers, what I am hoping for is an easy way to figure out if (given a scrambled arrangement of the original set) the new set is even or odd? Obviously other than the trivial solution of going through it permutation by permutation and counting.

Thanks for any input!

 

[verty]

The most basic odd permutations are those that swap 2 numbers. So count how many of those permutations must be applied to reach the identity. For example, 321 is odd (swap 3 and 1) but 312 is even (two swaps are required). It's a simple as that.

 

[vulpe]

I understand what odd and even permutations are, my question makes more sense if I use an example perhaps. Imagine that instead of 1,2,3 you have a set that's 1,2,3,4,5,6 . Now tell me, is 5,2,1,4,6,3 even or odd without taking forever haha :P

 

[dodo]

Hi, vulpe,
I'd attempt the swaps that put each peg in place. In your example,
5,2,1,4,6,3
1,2,5,4,6,3 (1,5)
1,2,3,4,6,5 (3,5)
1,2,3,4,5,6 (5,6)
hence this one is odd. At worst, you'd do as many swaps as elements are (minus 1, actually).

 

[Erland]

Go through all 2-element subsets of the numbers in the permutation and see for how many of these the greater number comes before the smaller in the permutation, call it an inversion if this is the case. If the number of inversions is odd, the permutaion is odd, otherwise even.

For example, in the permutation given by (2 6 1 4 3 5), (that is: 1 is mapped to 2, 2 to 6, 3 to 1, etc.) there are 6 inversions: (2,1), (6,1), (6,4), (6,3), (6,5), (4,3). 6 is en even number, so the permutation is even.

 

[eigenperson]

Another approach using the cycle structure.

In your example: the permutation taking 1, 2, 3, 4, 5, 6 to 5, 2, 1, 4, 6, 3 has cycle structure (1 5 6 3) (2) (4). (If you don't know how to write down the cycle structure of a permutation, learn!) Now, a 4-cycle is odd and a 1-cycle is even, so we have odd × even × even = odd, so the permutation is odd.