Background
The parity of a permutation, as defined by wikipedia, is as follows:
The sign or signature of a permutation σ is denoted sgn(σ) and defined as +1 if σ is even and −1 if σ is odd.
The sign of a permutation can be explicitly expressed as
sgn(σ) = (−1)^N(σ)
where N(σ) is the number of inversions in σ.
Alternatively, the sign of a permutation σ can be defined from its decomposition into the product of transpositions as
sgn(σ) = (−1)^m
where m is the number of transpositions in the decomposition.
For those of you who are not fond of Greek alphabet soup in their math, I'll try and simplify the definition a bit with an example (also stolen from wikipedia).
Example
Consider the input array {1, 2, 3, 4, 5}
, and a permutation of it, let's say, {3, 4, 5, 2, 1}
. In order to get from the original array to its permutation, you must swap indices 0
and 2
, 1
and 3
, then 2
and 4
. Although this is not a unique solution, the parity is well-defined so this works for all cases.
Since it requires 3 swaps, we label this permutation with an odd
parity. As you might expect, a permutation that requires an even amount of swaps is said to have an even
parity.
Challenge
Your challenge is to write a program in as few bytes as possible to determine the parity of a permutation. Your program or function must:
- Accept as arguments, two input arrays (or strings) representing a set before and after a permutation.
- Return or print the character
e
for even oro
for odd, given the permutation. - Should assume that all indices in the arrays or strings have unique values.
Test Cases
Assuming you declared a function named f
:
f([10], [10]) == "e"
f([10, 30, 20], [30, 20, 10]) == "e"
f([10, 30, 20, 40], [30, 20, 40, 10]) == "o"
This is code-golf, the shortest program in bytes wins!
[10], [10] -> e
(zero transpositions).[10 30 20], [30 20 10] -> e
(two transpositions).[10 30 20 40], [30 20 40 10] -> o
(three transpositions) \$\endgroup\$