15
\$\begingroup\$

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!

\$\endgroup\$
7
  • 4
    \$\begingroup\$ People won't like the strict output format. How about truthy for even and falsy for odd? (or the other way around) \$\endgroup\$ Mar 20, 2016 at 2:47
  • \$\begingroup\$ 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. \$\endgroup\$ Mar 20, 2016 at 2:49
  • \$\begingroup\$ @CatsAreFluffy is that better? \$\endgroup\$ Mar 20, 2016 at 2:51
  • \$\begingroup\$ Well, I guess we'll see! \$\endgroup\$ Mar 20, 2016 at 2:53
  • \$\begingroup\$ 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) \$\endgroup\$
    – Luis Mendo
    Mar 20, 2016 at 5:11

9 Answers 9

7
\$\begingroup\$

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.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ That is impressively small. Kudos! \$\endgroup\$ Mar 20, 2016 at 15:23
6
\$\begingroup\$

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 
\$\endgroup\$
7
  • 1
    \$\begingroup\$ This is a really clever solution! \$\endgroup\$
    – Alex A.
    Mar 20, 2016 at 4:46
  • \$\begingroup\$ @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. \$\endgroup\$
    – Luis Mendo
    Mar 20, 2016 at 5:00
  • 1
    \$\begingroup\$ You should add modular indexing to MATL. That would save 3 bytes here. \$\endgroup\$
    – Dennis
    Mar 20, 2016 at 15:16
  • \$\begingroup\$ @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 \$\endgroup\$
    – Luis Mendo
    Mar 20, 2016 at 16:13
  • \$\begingroup\$ ...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! \$\endgroup\$
    – Luis Mendo
    Mar 20, 2016 at 16:22
5
\$\begingroup\$

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)
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Good idea to use the determinants. Ole! \$\endgroup\$
    – Luis Mendo
    Mar 20, 2016 at 16:15
5
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can write cycle"eo"!!... Instead of "eo"!!mod(...)2, saving one byte. \$\endgroup\$ Mar 20, 2016 at 11:16
  • \$\begingroup\$ You can write this as g m=cycle"eo"!!sum[0|(a,b)<-m,(c,d)<-m,a<c,b>d];f=(g.).zip, I don't know if this would have counted as a 2 byte saving at the time, but it does now. \$\endgroup\$
    – Wheat Wizard
    Jun 26, 2022 at 8:48
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Interesting place for a comma.. didn't know you could do that. Don't forget about currying for -1 byte \$\endgroup\$ Mar 20, 2016 at 12:13
2
\$\begingroup\$

Mathematica, 77 bytes

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

I agree!

\$\endgroup\$
2
  • \$\begingroup\$ Handy function, unfortunately long name! \$\endgroup\$ Mar 20, 2016 at 3:01
  • \$\begingroup\$ Annoying, right? I hate Cycles. It bumps up the size of PermutationCycles's name, and even PermutationCycles is stupid, returning a Cycles object! ` \$\endgroup\$ Mar 20, 2016 at 3:05
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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