Parity of a Permutation

Question

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 or o 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!

Answer 1

Jelly, 13 12 bytes

żṗ2</€⁺Sị“oe

Try it online!

How it works

żṗ2</€⁺Sị“oe  Main link. Arguments: A, B (lists)

ż             Zip A with B. Yields an array of pairs [x, σ(x)].
 ṗ2           Generate all pairs [[x, σ(x)], [y, σ(y)]].
   </€        Reduce each pair by </€.
              This maps [[x, σ(x)], [y, σ(y)]] to [x < y, σ(x) < σ(y)].
      ⁺       Repeat the previous link, i.e., execute </€ once more.
              This maps [x < y, σ(x) < σ(y)] to ((x < y) < (σ(x) < σ(y))), which is
              true if and only if x > y and σ(x) < σ(y).
       S      Sum. This counts the number of inversions.
        ị“oe  Retrieve the letter at the corresponding index.
              Indexing is 1-based and modular, so an odd sum retrieves the first
              letter, an even sum the second.

Answer 2

MATL, 17 16 bytes

1 byte removed thanks to a suggestion by Dennis

2$St!<Rz2\'oe'w)

This works in current version (15.0.0) of the language.

Try it online!

Explanation

This uses the definition of parity in terms of inversions. An inversion is a pair of elements in the second array that are in the "wrong" order compared with the first array. Since the first array need not be sorted, we first sort it and the same rearrangement needed for that sorting is applied to the second array. Then an inversion corresponds to a pair of elements that is not increasing in the second array.

Note also that the two input arrays can be swapped and the result is the same. So it's not important which array is considered to be the "original" and which the "permuted".

2$S     % implicitly take two row vectors. Sort second and apply the indices
        % of that sorting to the first
t!      % duplicate. Transpose into column vector
<       % true for elements of the column vector that exceed those of the 
        % row vector. Gives a 2D array with all pairs of comparisons
R       % keep only upper triangular part of that array
z       % number of nonzero elements. This is the number of inversions
2\      % parity of that number: gives 0 or 1
'oe'w   % push string 'eo' below the top of the stack
)       % apply index to produce 'e' or 'o'. An index 1 refers to the first
        % element, whereas 0 refers to the last. Implicitly display 

Answer 3

Octave, 56 52 bytes

It seems nobody is using this approach so far: Basically I'm just using the determinants of the corresponding permutation matrices. The expression det(eye(nnz(a))(a,:)) returns the determinant of the permutation matrix defined by the vector a. Then it is just a matter of extracting the right character from the string, depending on the result.

p=@(v)eye(nnz(v))(v,:);@(a,b)'ole'(det(p(a)*p(b))+2)

Answer 4

Haskell, 58 bytes

k%l|m<-zip k l=cycle"eo"!!sum[1|(a,b)<-m,(c,d)<-m,a<c,b>d]

Usage:

*Main> [8,3,5]%[5,3,8]
'o'

Same method as my Python answer. proud haskeller saved a byte with cycle.

Alternative from Wheat Wizard for 58 bytes (56 by modern convention of removing f=):

g m=cycle"eo"!!sum[0|(a,b)<-m,(c,d)<-m,a<c,b>d]
f=(g.).zip

Answer 5

Python 2, 68 bytes

lambda*M:"eo"[sum(a<b<M>A>B for a,A in zip(*M)for b,B in zip(*M))%2]

Usage:

>>> f=lambda*M:"eo"[sum(a<b<M>A>B for a,A in zip(*M)for b,B in zip(*M))%2]
>>> f([8,3,5],[5,3,8])
'o'

Counts the number of inversion pairs of two zipped lists, i,e. values (a,A) and (b,B) from each list at the same index with a<b and A>B. These comparisons are combines as a<b<M>A>B, using the property that the list M is greater than any number. The sum is then taken modulo 2 and turned into e or o.

Answer 6

JavaScript (ES6), 73 bytes

(a,b)=>"eo"[r=0,g=a=>a.map((e,i)=>a.slice(i).map(d=>r^=d<e)),g(a),g(b),r]

Since we're only interested in the parity, any duplicate transpositions simply cancel out. Conveniently JavaScript's array subscripts are not multidimensional.

Answer 7

Mathematica, 77 bytes

If[Mod[Plus@@Length/@(Join[{0},#]&)/@PermutationCycles[#][[1]],2]==0,"e","o"]&

I agree!

Answer 8

Mathematica, 31 bytes

If[Tr[Signature/@{##}]==0,o,e]&

Signature[list] gives the signature of the permutation needed to place the elements of list in canonical order

We can reorder one list to the other, by first reordering one list to any order (in this case the canonical order) and reorder this list to the final list. The sign of the overall permutation is even, iff the signs of the two sub-permutations are equal.

Answer 9

05AB1E, 13 bytes

øDδ›Æ0›˜O„eoè

Try it online or verify all test cases.

Or alternatively:

øãε`›`›}O„eoè

Try it online or verify all test cases.

Both ports of @Dennis' Jelly answer, so make sure to upvote him as well!

Explanation:

ø             # Zip to pair the values in the two (implicit) input-lists together
 D            # Duplicate this list of pairs
  δ           # Apply double-vectorized with the two lists:
   ›          #  > check
              #   (e.g. [a,b] and [c,d] → [a>c,b>d]
    Æ         # Reduce each inner-most pair by subtracting: [a>c,b>d] → (a>c)-(b>d)
     0›       # Check if it's positive: (a>c)-(b>d)>0
       O      # Sum these checks together
           è  # Modular 0-based index it into
        „eo   # string "eo"
              # (which is output implicitly as result)

ø             # Same as above
 ã            # Cartesian product with itself to create pairs of pairs
  ε           # Map over each pair of pairs:
   `          #  Pop and push both pairs to the stack
    ›         #  [a,b] and [c,d] → [a>c,b>d]
     `        #  Pop these values to the check again
      ›       #  (a>c) and (b>d) → (a>c)>(b>d)
  }           # Close the map
   O„eoè      # Same as above, including implicit output

Minor note: Jelly uses 1-based indexing and 05AB1E uses 0-based, which is why his string is "oe" and mine is "eo".