Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 , the shortest program in bytes wins!

share|improve this question
3  
People won't like the strict output format. How about truthy for even and falsy for odd? (or the other way around) – CalculatorFeline Mar 20 at 2:47
    
I was actually hoping to retain the output format I specified unless anyone else really is bothered by it. Edit hold on, I'll compromise. – Patrick Roberts Mar 20 at 2:49
    
@CatsAreFluffy is that better? – Patrick Roberts Mar 20 at 2:51
    
Well, I guess we'll see! – CalculatorFeline Mar 20 at 2:53
    
Good night! Here are some suggestions for when you come back to this (but please do check yourself): [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) – Luis Mendo Mar 20 at 5:11
up vote 4 down vote accepted

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.
share|improve this answer
1  
That is impressively small. Kudos! – Patrick Roberts Mar 20 at 15:23

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 
share|improve this answer
1  
This is a really clever solution! – Alex A. Mar 20 at 4:46
    
@AlexA. Thanks! I've edited the answer to clarify what the pre-ordering part does: we sort one array and then the same rearrangement needed for that sorting is applied to the other array. – Luis Mendo Mar 20 at 5:00
    
You should add modular indexing to MATL. That would save 3 bytes here. – Dennis Mar 20 at 15:16
    
@Dennis Yes, I've often thought about that... but currently it uses a format where negative values have a different meaning. I chose that in order to have indices of the form x(1:end-2) etc without explicitly indicating the size of x. Not sure if it was a good choice, but I guess it's too late to change now :-) Maybe I'll find a compatible way to add modular indexing – Luis Mendo Mar 20 at 16:13
    
...and indices exceeding current length are used to assign new values. But index 0 does have the meaning of "last entry", so I can save a byte (remove the increment). Thanks for the idea! – Luis Mendo Mar 20 at 16:22

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.

share|improve this answer

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.

share|improve this answer
1  
Interesting place for a comma.. didn't know you could do that. Don't forget about currying for -1 byte – Patrick Roberts Mar 20 at 12:13

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)
share|improve this answer
2  
Good idea to use the determinants. Ole! – Luis Mendo Mar 20 at 16:15

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.

share|improve this answer
    
You can write cycle"eo"!!... Instead of "eo"!!mod(...)2, saving one byte. – proud haskeller Mar 20 at 11:16

Mathematica, 77 bytes

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

I agree!

share|improve this answer
    
Handy function, unfortunately long name! – Patrick Roberts Mar 20 at 3:01
    
Annoying, right? I hate Cycles. It bumps up the size of PermutationCycles's name, and even PermutationCycles is stupid, returning a Cycles object! ` – CalculatorFeline Mar 20 at 3:05

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.