Antecedentes

La paridad de una permutación , según lo define wikipedia , es la siguiente:

El signo o firma de una permutación σ se denota sgn (σ) y se define como +1 si σ es par y −1 si σ es impar.

El signo de una permutación puede expresarse explícitamente como

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

donde N (σ) es el número de inversiones en σ.

Alternativamente, el signo de una permutación σ se puede definir a partir de su descomposición en el producto de transposiciones como

sgn (σ) = (−1) ^ m

donde m es el número de transposiciones en la descomposición.

Para aquellos de ustedes que no son aficionados a la sopa del alfabeto griego en sus matemáticas, intentaré simplificar un poco la definición con un ejemplo (también robado de wikipedia).

Ejemplo

Considere la matriz de entrada {1, 2, 3, 4, 5}, y una permutación de ella, digamos, {3, 4, 5, 2, 1}. Para pasar de la matriz original a su permutación, debe intercambiar índices 0y 2, 1y 3, luego 2y 4. Aunque esta no es una solución única, la paridad está bien definida, por lo que funciona para todos los casos.

Como requiere 3 intercambios, etiquetamos esta permutación con una oddparidad. Como es de esperar, se dice que una permutación que requiere una cantidad pareja de intercambios tiene una evenparidad.

Desafío

Su desafío es escribir un programa en la menor cantidad de bytes posible para determinar la paridad de una permutación. Su programa o función debe:

• Acepte como argumentos, dos matrices de entrada (o cadenas) que representan un conjunto antes y después de una permutación.
• Devuelve o imprime el carácter epar o oimpar, dada la permutación.
• Debe suponer que todos los índices en las matrices o cadenas tienen valores únicos.

Casos de prueba

Asumiendo que declaró una función llamada f:

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

Este es el código de golf , ¡el programa más corto en bytes gana!

Jalea, 13 12 bytes

żṗ2</€⁺Sị“oe

Pruébalo en línea!

Cómo funciona

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

1 byte eliminado gracias a una sugerencia de Dennis

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

Esto funciona en la versión actual (15.0.0) del lenguaje.

Pruébalo en línea !

Explicación

Esto usa la definición de paridad en términos de inversiones. Una inversión es un par de elementos en la segunda matriz que están en el orden "incorrecto" en comparación con la primera matriz. Como no es necesario ordenar la primera matriz, primero la clasificamos y la misma reorganización necesaria para esa clasificación se aplica a la segunda matriz. Entonces, una inversión corresponde a un par de elementos que no aumentan en la segunda matriz.

Tenga en cuenta también que las dos matrices de entrada se pueden intercambiar y el resultado es el mismo. Por lo tanto, no es importante qué matriz se considera "original" y cuál "permutado".

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 

Octava, 56 52 bytes

Parece que nadie está usando este enfoque hasta ahora: Básicamente solo estoy usando los determinantes de las matrices de permutación correspondientes. La expresión det(eye(nnz(a))(a,:))devuelve el determinante de la matriz de permutación definida por el vector a. Entonces es solo cuestión de extraer el carácter correcto de la cadena, dependiendo del resultado.

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]

Uso:

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

El mismo método que mi respuesta de Python . orgulloso haskeller salvó un byte con 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]

Uso:

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

Cuenta el número de pares de inversión de dos listas comprimidas, i, e. valores (a,A)y (b,B)de cada lista en el mismo índice con a<by A>B. Estas comparaciones se combinan como a<b<M>A>B, utilizando la propiedad de que la lista Mes mayor que cualquier número. Luego se toma la suma del módulo 2 y se convierte en eo o.

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]

Como solo estamos interesados ​​en la paridad, cualquier transposición duplicada simplemente se cancela. Convenientemente, los subíndices de matriz de JavaScript no son multidimensionales.

Mathematica, 77 bytes

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

¡Estoy de acuerdo!

Mathematica, 31 bytes

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

Firma [lista] proporciona la firma de la permutación necesaria para colocar los elementos de la lista en orden canónico

Podemos reordenar una lista a la otra, primero reordenando una lista a cualquier orden (en este caso el orden canónico) y reordenar esta lista a la lista final. El signo de la permutación general es par, si los signos de las dos subpermutaciones son iguales.