Contexte

La parité d'une permutation , telle que définie par wikipedia , est la suivante:

Le signe ou la signature d'une permutation σ est noté sgn (σ) et défini comme +1 si σ est pair et -1 si σ est impair.

Le signe d'une permutation peut être explicitement exprimé comme

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

où N (σ) est le nombre d'inversions dans σ.

Alternativement, le signe d'une permutation σ peut être défini à partir de sa décomposition en produit de transpositions comme

sgn (σ) = (−1) ^ m

où m est le nombre de transpositions dans la décomposition.

Pour ceux d'entre vous qui n'aiment pas la soupe à l'alphabet grec dans leurs mathématiques, je vais essayer de simplifier un peu la définition avec un exemple (également volé sur wikipedia).

Exemple

Considérons le tableau d'entrée {1, 2, 3, 4, 5}, et une permutation de celui - ci, disons, {3, 4, 5, 2, 1}. Pour passer du tableau d'origine à sa permutation, vous devez permuter les indices 0et 2, 1et 3, puis 2et 4. Bien que ce ne soit pas une solution unique, la parité est bien définie, donc cela fonctionne pour tous les cas.

Puisqu'elle nécessite 3 swaps, nous étiquetons cette permutation avec une oddparité. Comme vous pouvez vous y attendre, une permutation qui nécessite une quantité égale de swaps est réputée avoir une evenparité.

Défi

Votre défi est d'écrire un programme en aussi peu d'octets que possible pour déterminer la parité d'une permutation. Votre programme ou fonction doit:

• Acceptez comme arguments, deux tableaux (ou chaînes) d'entrée représentant un ensemble avant et après une permutation.
• Retourne ou imprime le caractère epair ou oimpair, compte tenu de la permutation.
• Devrait supposer que tous les indices des tableaux ou des chaînes ont des valeurs uniques.

Cas de test

En supposant que vous ayez déclaré une fonction nommée f:

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

C'est le code-golf , le programme le plus court en octets gagne!

Gelée, 13 12 octets

żṗ2</€⁺Sị“oe

Essayez-le en ligne!

Comment ça fonctionne

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

1 octet supprimé grâce à une suggestion de Dennis

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

Cela fonctionne en la version actuelle (15.0.0) de la langue.

Essayez-le en ligne !

Explication

Celui-ci utilise la définition de la parité en termes d'inversions. Une inversion est une paire d'éléments du deuxième tableau qui sont dans le "mauvais" ordre par rapport au premier tableau. Puisque le premier tableau n'a pas besoin d'être trié, nous le trions d'abord et le même réarrangement nécessaire pour ce tri est appliqué au second tableau. Ensuite, une inversion correspond à une paire d'éléments qui n'augmente pas dans le deuxième tableau.

Notez également que les deux tableaux d'entrée peuvent être échangés et le résultat est le même. Il n'est donc pas important de savoir quel tableau est considéré comme "original" et lequel est "permuté".

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 

Octave, 56 52 octets

Il semble que personne n'utilise cette approche jusqu'à présent: en gros, j'utilise simplement les déterminants des matrices de permutation correspondantes. L'expression det(eye(nnz(a))(a,:))renvoie le déterminant de la matrice de permutation définie par le vecteur a. Ensuite, il suffit d'extraire le bon caractère de la chaîne, selon le résultat.

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

Haskell, 58 octets

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'

Même méthode que ma réponse Python . fier haskeller a enregistré un octet avec cycle.

Python 2, 68 octets

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'

Compte le nombre de paires d'inversion de deux listes zippées, i, e. valeurs (a,A)et (b,B)de chaque liste au même index aveca<b et A>B. Ces comparaisons sont combinées en a<b<M>A>Butilisant la propriété que la liste Mest supérieure à n'importe quel nombre. La somme est alors prise modulo 2 et transformée en eou o.

JavaScript (ES6), 73 octets

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

Étant donné que nous ne sommes intéressés que par la parité, toute transposition en double est simplement annulée. De manière pratique, les indices de tableau de JavaScript ne sont pas multidimensionnels.

Mathematica, 77 octets

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

Je suis d'accord!

Mathematica, 31 octets

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

Signature [liste] donne la signature de la permutation nécessaire pour placer les éléments de la liste dans l'ordre canonique

Nous pouvons réorganiser une liste à l'autre, en réordonnant d'abord une liste à n'importe quel ordre (dans ce cas, l'ordre canonique) et réorganiser cette liste à la liste finale. Le signe de la permutation globale est pair, si les signes des deux sous-permutations sont égaux.