Muchos temas importantes en álgebra abstracta implican una función binaria que actúa sobre un conjunto. Se han definido una serie de propiedades de tales funciones en la investigación de dichos temas.
Su desafío será determinar si una función binaria dada en un dominio dado posee cinco de estas propiedades.
Propiedades
Una función binaria se cierra si cada salida posible está en el dominio.
Una función binaria es asociativa si el orden en que se aplica la función a una serie de entradas no afecta el resultado. Es decir, $
es asociativo si (a $ b) $ c
siempre es igual a $ (b $ c)
. Tenga en cuenta que, dado que el valor (a $ b)
se utiliza como entrada, las funciones asociativas deben cerrarse.
Una función binaria es conmutativa si intercambiar el orden de las entradas no cambia el resultado. En otras palabras, si a $ b
siempre es igual b $ a
.
Una función binaria tiene un elemento de identidad si existe algún elemento e
en el dominio tal que a $ e = a = e $ a
para todos a
en el dominio.
Una función binaria es idempotente si aplicarla a dos entradas idénticas da ese número como salida. En otras palabras, si a $ a = a
para todos a
en el dominio.
Entrada
Se le dará una función en forma de matriz, y el dominio de la función serán los números 0 ... n-1
, donde n
está la longitud lateral de la matriz.
El valor (a $ b)
está codificado en la matriz como el elemento a
th de la fila b
th. Si la matriz de entrada es Q
, entonces a $ b
=Q[a][b]
Por ejemplo, la función de exponenciación ( **
en Python) en el dominio [0, 1, 2]
está codificada como:
[[1, 0, 0]
[1, 1, 1]
[1, 2, 4]]
Los dominios izquierdo y derecho son iguales, por lo que la matriz siempre será cuadrada.
Puede utilizar cualquier formato de matriz conveniente como entrada, como una lista de listas, una lista única en orden principal de fila o columna, el objeto de matriz nativo de su idioma, etc. Sin embargo, no puede tomar una función directamente como entrada.
Para simplificar, las entradas de la matriz serán todas enteras. Puede suponer que encajan en el tipo entero nativo de su idioma.
Salida
Puede indicar cuáles de las propiedades anteriores tienen el formato que elija, incluida una lista de booleanos, una cadena con un carácter diferente para cada propiedad, etc. Sin embargo, debe haber una salida única y distinta para cada uno de los 24 subconjuntos posibles de las propiedades. Esta salida debe ser fácilmente legible por humanos.
Ejemplos
La función máxima en el dominio n = 4:
[[0, 1, 2, 3]
[1, 1, 2, 3]
[2, 2, 2, 3]
[3, 3, 3, 3]]
Esta función tiene las propiedades de cierre, asociatividad, conmutatividad, identidad e idempotencia.
La función de exponenciación en el dominio n = 3:
[[1, 0, 0]
[1, 1, 1]
[1, 2, 4]]
Esta función no tiene ninguna de las propiedades anteriores.
La función de suma en el dominio n = 3:
[[0, 1, 2]
[1, 2, 3]
[2, 3, 4]]
Esta función tiene las propiedades de conmutatividad e identidad.
El combinador K en el dominio n = 3:
[[0, 0, 0]
[1, 1, 1]
[2, 2, 2]]
Esta función tiene las propiedades de cierre, asociatividad e idempotencia.
La función de diferencia absoluta en el dominio n = 3:
[[0, 1, 2]
[1, 0, 1]
[2, 1, 0]]
Esta función tiene las propiedades de cierre, conmutatividad e identidad.
La función promedio, redondeando hacia pares, en el dominio n = 3:
[[0, 0, 1]
[0, 1, 2]
[1, 2, 2]]
Esta función tiene las propiedades de cierre, conmutatividad, identidad e idempotencia.
La función de igualdad en el dominio n = 3:
[[1, 0, 0]
[0, 1, 0]
[0, 0, 1]]
Esta función tiene las propiedades de cierre y conmutatividad.
Desafío
Este es el código de golf. Se aplican lagunas estándar . Menos bytes gana.
c=all(l>)
?[i%i|i<-b]==b
.CJam, 95 bytes
Imprime una subsecuencia de
*AC1I
.*
es el símbolo de cierre ,A
es asociativo ,C
es conmutativo ,1
es de identidad yI
es idempotente .La matriz de entrada se lee
q~
y se almacena en A (:A
).Cierre
Si todos los
:*
elementos ( ) en la matriz (Ae_
) son más pequeñosf<
que B = tamaño (A) (A,:B
), imprima a*
('**
).Asociatividad
Genera todos los triples en el dominio (
B3m*
). ImprimimosA
si todos cumplen una condición ({...}%:*'A*
).La condición es que, para algunos triples
[i j k]
, el plegado a la izquierda que enumera con A (_{A==}*
) y el plegado a la izquierda su reverso[k j i]
(\W%
) con A op ({Az==}*
), la versión invertida deA
, son iguales (=
).Conmutatividad
A debe ser igual a su transpuesta:
A_z=
. Si es así, imprimimosC
('C=
).Identidad
La identidad es necesariamente única, por lo que solo podemos imprimir una
1
.Idempotente
Comprueba si la diagonal es igual
B,
. Si es así, imprima unI
.fuente
Matlab, 226
Una cosa importante a notar es que no cerrado implica no asociativo. Muchas de esas propiedades se pueden verificar fácilmente usando algunas propiedades de la matriz:
De entrada a través de Matlab standar notación:
[a,b;c,d]
o[[a,b];[c,d]]
o[a b;c d]
etc.La salida es un vector de unos a ceros, 1 = verdadero, 0 = falso, para cada una de las propiedades en el orden dado.
Código completo:
fuente
JavaScript (ES6) 165
Una función anónima que devuelve una matriz con cinco valores 0/1, que están en orden Cierre, asociatividad, conmutatividad, identidad e idempotencia.
Menos golf
Prueba
fuente