Hintergrund

Die Parität einer Permutation , wie in Wikipedia definiert , ist wie folgt:

Das Vorzeichen oder die Signatur einer Permutation σ wird als sgn (σ) bezeichnet und als +1 definiert, wenn σ gerade ist, und -1, wenn σ ungerade ist.

Das Vorzeichen einer Permutation kann explizit ausgedrückt werden als

sgn (σ) = (−1) ^ N (σ)

wobei N (σ) die Anzahl der Inversionen in σ ist.

Alternativ kann das Vorzeichen einer Permutation σ aus ihrer Zerlegung in das Produkt der Transpositionen als definiert werden

sgn (σ) = (−1) ^ m

wobei m die Anzahl der Transpositionen bei der Zerlegung ist.

Für diejenigen von euch, die griechische Buchstabensuppe in ihrer Mathematik nicht mögen, werde ich versuchen, die Definition ein wenig mit einem Beispiel zu vereinfachen (auch aus Wikipedia gestohlen).

Beispiel

Betrachten wir das Eingabearray {1, 2, 3, 4, 5}und eine Permutation davon {3, 4, 5, 2, 1}. Um vom ursprünglichen Array zur Permutation zu gelangen, müssen Sie die Indizes 0und 2, 1und 3, dann 2und vertauschen 4. Obwohl dies keine eindeutige Lösung ist, ist die Parität genau definiert, sodass dies in allen Fällen funktioniert.

Da es 3 Swaps erfordert, kennzeichnen wir diese Permutation mit einer oddParität. Wie zu erwarten ist, hat eine Permutation, die eine gerade Anzahl von Swaps erfordert, eine evenParität.

Herausforderung

Ihre Herausforderung besteht darin, ein Programm in möglichst wenigen Bytes zu schreiben, um die Parität einer Permutation zu bestimmen. Ihr Programm oder Ihre Funktion muss:

• Akzeptieren Sie als Argumente zwei Eingabearrays (oder Zeichenfolgen), die eine Menge vor und nach einer Permutation darstellen.
• Gibt das Zeichen efür gerade oder oungerade zurück oder druckt es aus, wenn die Permutation gegeben ist.
• Sollte davon ausgehen, dass alle Indizes in den Arrays oder Strings eindeutige Werte haben.

Testfälle

Angenommen, Sie haben eine Funktion mit dem Namen f: deklariert.

f([10], [10]) == "e"
f([10, 30, 20], [30, 20, 10]) == "e"
f([10, 30, 20, 40], [30, 20, 40, 10]) == "o"

Das ist Code-Golf , das kürzeste Programm in Bytes gewinnt!

Jelly, 13-12 Bytes

żṗ2</€⁺Sị“oe

Probieren Sie es online!

Wie es funktioniert

żṗ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.

MATL , 17 16 Bytes

Dank eines Vorschlags von Dennis wurde 1 Byte entfernt

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

Dies funktioniert in der aktuellen Version (15.0.0) der Sprache.

Probieren Sie es online !

Erläuterung

Dies verwendet die Definition der Parität in Bezug auf Inversionen. Eine Inversion ist ein Paar von Elementen im zweiten Array, die sich im Vergleich zum ersten Array in der "falschen" Reihenfolge befinden. Da das erste Array nicht sortiert werden muss, sortieren wir es zuerst und die gleiche Neuanordnung, die für diese Sortierung erforderlich ist, wird auf das zweite Array angewendet. Dann entspricht eine Inversion einem Elementpaar, das im zweiten Array nicht zunimmt.

Beachten Sie auch, dass die beiden Eingabearrays vertauscht werden können und das Ergebnis dasselbe ist. Es ist also nicht wichtig, welches Array als "Original" und welches als "permutiert" angesehen wird.

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 

Oktave, 56 52 Bytes

Bisher scheint niemand diesen Ansatz zu verwenden: Grundsätzlich verwende ich nur die Determinanten der entsprechenden Permutationsmatrizen. Der Ausdruck det(eye(nnz(a))(a,:))gibt die Determinante der durch den Vektor definierten Permutationsmatrix zurück a. Dann muss nur noch das richtige Zeichen aus der Zeichenfolge extrahiert werden, abhängig vom Ergebnis.

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

Haskell, 58 Bytes

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

Verwendung:

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

Gleiche Methode wie meine Python-Antwort . stolzer haskeller hat ein byte mit gespeichert cycle.

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]

Verwendung:

>>> 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'

Zählt die Anzahl der Inversionspaare von zwei gezippten Listen, d.h. Werte (a,A)und (b,B)aus jeder Liste am gleichen Index mit a<bund A>B. Diese Vergleiche werden kombiniert a<b<M>A>B, indem die Eigenschaft verwendet wird, dass die Liste Mgrößer als eine beliebige Zahl ist. Die Summe wird dann modulo 2 genommen und in eoder umgewandelt o.

JavaScript (ES6), 73 Byte

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

Da wir nur an der Parität interessiert sind, werden doppelte Transpositionen einfach aufgehoben. Bequemerweise sind die Array-Indizes von JavaScript nicht mehrdimensional.

Mathematica, 77 Bytes

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

Genau!

Mathematica, 31 Bytes

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

Signatur [Liste] gibt die Signatur der Permutation an, die erforderlich ist, um die Elemente der Liste in kanonische Reihenfolge zu bringen

Wir können eine Liste in die andere umordnen, indem wir zuerst eine Liste in eine beliebige Reihenfolge (in diesem Fall die kanonische Reihenfolge) umordnen und diese Liste in die endgültige Liste umordnen. Das Vorzeichen der Gesamtpermutation ist gerade, wenn die Vorzeichen der beiden Unterpermutationen gleich sind.