Permutaciones conjugadas

17

Una permutación de tamaño n es un reordenamiento de los primeros n enteros positivos. (lo que significa que cada número entero aparece una vez y exactamente una vez). Las permutaciones pueden tratarse como funciones que cambian el orden de una lista de elementos de tamaño n . Por ejemplo

(4 1 2 3) ["a", "b", "c", "d"] = ["d", "a", "b", "c"]

Así, las permutaciones se pueden componer como funciones.

(4 1 2 3)(2 1 3 4) = (4 2 1 3)

Esto trae consigo muchas propiedades interesantes. Hoy nos estamos centrando en la conjugación . Las permutaciones y y x (ambas de tamaño n ) son conjugados si hay permutaciones g y g -1 (también de tamaño n ) de modo que

x = gyg-1

y gg -1 es igual a la permutación de identidad (los primeros n números en el orden correcto).

Su tarea es tomar dos permutaciones del mismo tamaño a través de métodos de entrada estándar y decidir si son conjugados. Debe generar uno de dos valores consistentes, uno si son conjugados y el otro si no lo son.

Este es el código de golf, por lo que las respuestas se puntuarán en bytes con menos bytes mejor.

Hay muchos teoremas sobre permutaciones conjugadas que están a su disposición, así que buena suerte y feliz golf.

Puede tomar la entrada como un contenedor ordenado de valores (ya sea 1-n o 0-n) que representan la permutación como arriba, o como una función que toma un contenedor ordenado y realiza la permutación. Si elige tomar una función, debe tomarla como un argumento en lugar de tenerla con un nombre predefinido.

Casos de prueba

(1) (1) -> True
(1 2) (2 1) -> False
(2 1) (2 1) -> True
(4 1 3 2) (4 2 1 3) -> True
(3 2 1 4) (4 3 2 1) -> False 
(2 1 3 4 5 7 6) (1 3 2 5 4 6 7) -> True
code-golf decision-problem combinatorics permutations abstract-algebra Post Rock Garf Hunter
fuente
¿Podemos tomar la entrada como una función? ¿Podemos también tomar el tamaño n?
xnor
@xnor Claro en ambos aspectos. Sin embargo, no estoy seguro de cómo te ayudará el primero.
Post Rock Garf Hunter
Las reglas de entrada de función predeterminadas permiten suponer que la función está predefinida, lo que ahorra bytes al escribirla como argumento, si lo permite.
xnor
@xnor ¿Estamos hablando de esta regla? Eso es para funciones de recuadro negro que no son permutaciones. Esto tiene sentido porque ese consenso está diseñado para permitir que los lenguajes sin punteros / objetos de función compitan mientras que aquí pueden porque las permutaciones pueden representarse de otra manera.
Post Rock Garf Hunter
Lo estaba, no pensé en la distinción de que eran de caja negra. Entonces, ¿la entrada puede ser una función, pero solo como un argumento explícito?
xnor

Respuestas:

6

Python 2 , 87 bytes

f=lambda P,k:k<1or len({sum([x==eval('L['*k+'x'+']'*k)for x in L])for L in P})&f(P,k-1)

Pruébalo en línea!

Toma entrada Pcomo un par de ambas permutaciones y ksu longitud. Salidas 1para conjugados y 0no.

Esto usa el resultado:

Dos permutaciones x e y se conjugan exactamente si sus k -ésimas potencias x k e y k tienen el mismo número de puntos fijos por cada k de 0 a n .

Dos permutaciones conjugadas satisfacen esto porque sus poderes k también son conjugados, y la conjugación conserva el recuento de puntos fijos.

Es menos obvio que dos permutaciones no conjugadas siempre difieren. En particular, la conjugación está determinada por la lista ordenada de longitudes de ciclo, y estas pueden recuperarse de los recuentos de puntos fijos. Una forma de mostrar esto es con álgebra lineal, aunque podría ser excesivo.

Deje X ser la matriz de permutación para x . Entonces, el número de puntos fijos de x k es Tr (X k ) . Estas trazas son los polinomios simétricos de suma de potencia de los valores propios de X k con multiplicidad. Estos polinomios para k de 0 a n nos permiten recuperar los polinomios simétricos elementales correspondientes de estos valores propios, y por lo tanto el polinomio característico y, por lo tanto, los propios valores propios.

Dado que estos valores propios son raíces de unidad correspondientes a los ciclos de x , a partir de ellos podemos recuperar los tamaños de los ciclos y sus multiplicidades. Entonces, nuestra "firma" identifica la permutación hasta la conjugación.

xnor
fuente
6

J , 25 bytes 23 bytes 16 bytes

solución tácita de miles :

-:&([:/:~#&>)&C.

La solución explícita de OP:

c=:4 :'-://:~"1#&>C.&>x;y'

Esto verifica si las permutaciones xey tienen el mismo tipo de ciclo, utilizando la C.función incorporada para producir representaciones de ciclo.

   4 1 3 2   c   4 2 1 3
1
   3 2 1 4   c   4 3 2 1
0
   2 1 3 4 5 7 6   c   1 3 2 5 4 6 7
1
Mathias Dolidon
fuente
1
Bienvenido a PPCG y buen primer post. Acorté su método a 16 bytes -:&([:/:~#&>)&C.usando un formulario tácito. Aquí hay un enlace TIO para probarlo.
millas
Gracias. :) Todavía soy un principiante de J, y aunque parece que lo uso fácilmente con formas explícitas, componer formas tácitas eficientes aún requiere mucho pensamiento para mí. Agregaré tu solución.
Mathias Dolidon
PD: ¿no contamos también los caracteres de las asignaciones de funciones? c=:
Mathias Dolidon
1
@MathiasDolidon No, por consenso general, no contamos los caracteres necesarios para la asignación, ya que la función puede usarse tal cual (con paréntesis, pero no los contamos).
Erik the Outgolfer
1
OKAY ! He actualizado retroactivamente los recuentos de la solución explícita en el título para tener esto en cuenta.
Mathias Dolidon
4

MATL , 20 19 17 16 bytes

xY@!"&G@)@b)X=va

Entrada: dos vectores de columna (usando ;como separador). Salida: 1si se conjuga, 0si no.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

No se utilizan teoremas sobre permutaciones (por pura ignorancia); solo fuerza bruta y estos dos hechos:

  • Para dos permutaciones p y q , la composición pq es equivalente a usar p para indexar los elementos de q .

  • La condición x = gyg −1 es equivalente a xg = gy .

Código comentado:

x      % Implicitly input first permutation, x. Delete it. Gets copied into clipboard G
Y@     % Implicitly input second permutation, y. Push a matrix with all permutations
       % of its elements, each permutation on a different row. So each matrix row is
       % a permutation of [1 2 ...n], where n is the size of y
!      % Transpose. Now each permutation is a column
"      % For each column
  &G   %   Push x, then y
  @    %   Push current column. This is a candidate g permutation
  )    %   Reference indexing. This gives g composed with y
  @    %   Push current column again
  b    %   Bubble up. Moves x to the top of the stack
  )    %   Reference indexing. This gives x composed with g
  X=   %   Are they equal as vectors? Gives true or false
  v    %   Concatenate stack so far. The stack contains the latest true/false result
       %   and possibly the accumulated result from previous iterations
  a    %   Any: gives true if any element is true. This is the "accumulating" function
       % Implicit end. Implicit display
Luis Mendo
fuente
2

Jalea , 11 bytes

Œ!©Ụ€ịị"®⁸e

Pruébalo en línea!

Cómo funciona

Œ!©Ụ€ịị"®⁸e  Main link. Left argument: x. Right argument: y

Œ!©          Take all permutations g of x. Copy the result to the register.
   Ụ€        Grade up each; sort the indices of each permutation g by their
             corresponding values. For permutations of [1, ..., n], grading up
             essentially computes the inverse, g⁻¹.
     ị       Let each g⁻¹ index into y, computing g⁻¹y.
      ị"®    Let the results index into the corresponding g, computing g⁻¹yg.
         ⁸e  Test if x occurs in the result.
Dennis
fuente
Por lo que entiendo, en realidad es lo yque se indexa en cada uno g⁻¹, no al revés. Ver el ejemplo (4 1 2 3)(2 1 3 4) = (4 2 1 3),. Con su enfoque, daría como resultado (1 4 2 3), ya que el segundo se indexa en el primero. Teniendo eso en cuenta, tengo una solución de 12 bytes que todavía no estropearé. :-)
Erik the Outgolfer
@EriktheOutgolfer Fijo.
Dennis
@ Dennis Pero no llegué a esa conclusión basándome en la explicación, llegué exactamente al mismo enfoque, excepto que tenía algo como Œ!©Ụ€⁹ịЀ®ị"⁸e(básicamente todo indexado con argumentos invertidos), excepto más corto después de que hice modificaciones importantes. No creo que g⁻¹ygsea ​​lo mismo que gyg⁻¹. Además, creo que su respuesta también puede beneficiarse de esas modificaciones, pero, como dije antes, todavía no quiero arruinar la diversión.
Erik the Outgolfer
Sí, es exactamente lo mismo. Si x = g⁻¹yg, entonces gxg⁻¹ = y, así xy yson conjugados.
Dennis
Hm, siento que debería revelar mi solución de 12 bytes:eŒ!ị"Ụị@¥€¥¥
Erik the Outgolfer
1

Casco , 9 bytes

¤¦ṠmöLU¡!

Devuelve 1para conjugado y 0para no conjugado. Pruébalo en línea!

Explicación

La clase de conjugación de una permutación P de L = [1,2, .., n] está determinada por el conjunto múltiple que contiene el período mínimo de cada número en L bajo P . Cuando P se toma en formato de lista, puedo reemplazar L con P y obtener el mismo conjunto múltiple. El programa calcula el conjunto múltiple correspondiente para cada entrada y comprueba si uno es un subconjunto múltiple de la otra. Como tienen el mismo número de elementos, esto es equivalente a ser el mismo conjunto múltiple.

¤¦ṠmöLU¡!  Implicit inputs: two lists of integers.
¤          Apply one function to both and combine with another function.
  ṠmöLU¡!  First function. Argument: a list P.
  Ṡm       Map this function over P:
       ¡!  iterate indexing into P,
      U    take longest prefix with unique elements,
    öL     take its length.
 ¦         Combining function: is the first list a subset of the other, counting multiplicities?
Zgarb
fuente
1

Perl, 61 58 57 bytes

Incluye +2paraap

Dé permutaciones basadas en 0 como 2 líneas en STDIN

perl -ap '$_=[@1]~~[@1=map{-grep$_-$G[$i++%@G],@F=@G[@F]}@G=@F,0]'
3 0 2 1
3 1 0 2
^D

El algoritmo es una variación menor de la solución de xnor

Esta versión anterior del código golpea un error de Perl y vuelca el núcleo de varias entradas en mi último Perl 5.26.1, pero funciona en un Perl anterior5.16.3 .

@{$.}=map{-grep$_==$F[$i++%@F],@G=@F[@G]}@G=@F,0}{$_=@1~~@2

Posiblemente sea otra instancia más de mi antiguo enemigo perlgolf, el hecho de que perl no cuenta correctamente su pila.

Ton Hospel
fuente
1

JavaScript (ES6), 66 64 bytes

(a,b,g=a=>b+a.map(h=(e,i)=>e-i&&1+h(a[e],i)).sort())=>g(a)==g(b)

Si he leído las otras respuestas correctamente, el problema es equivalente a contar los períodos de todos los elementos y verificar que las dos listas tengan el mismo número de cada período. Editar: guardado 1 byte gracias a @Arnauld calculando uno menos que el período. Ahorré otro byte gracias a @Arnauld al abusar de las extrañas reglas de coerción de JavaScript para comparar las matrices. Otro byte podría salvarse al curry, pero no me gusta el curry a menos que sea pollo tikka masala.

Neil
fuente