Propiedades de las funciones binarias.

14

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

Cierre

Una función binaria se cierra si cada salida posible está en el dominio.

Asociatividad

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) $ csiempre es igual a $ (b $ c). Tenga en cuenta que, dado que el valor (a $ b)se utiliza como entrada, las funciones asociativas deben cerrarse.

Conmutatividad

Una función binaria es conmutativa si intercambiar el orden de las entradas no cambia el resultado. En otras palabras, si a $ bsiempre es igual b $ a.

Identidad

Una función binaria tiene un elemento de identidad si existe algún elemento een el dominio tal que a $ e = a = e $ apara todos aen el dominio.

Idempotencia

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 = apara todos aen 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 nestá la longitud lateral de la matriz.

El valor (a $ b)está codificado en la matriz como el elemento ath de la fila bth. 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.

isaacg
fuente

Respuestas:

4

Pyth, 51 bytes

[qKUQ@VQKCIQ}]Km{@RdCBQKJ!-sQK&JqF.bsm@[email protected],sQK

Pruébelo en línea: Demostración o conjunto de pruebas

Esto imprime una lista de 5 valores booleanos. Indican las propiedades en el orden:

[Idempotence, Commutativity, Identity, Closure, Associativity]

Aquí hay un mejor formato de salida: Demonstration o Test Suite

Explicación:

Idempotencia:

qKUQ@VQK
   Q       Q = input matrix
  UQ       [0, 1, ..., len(matrix)-1]
 K         assign to K
    @VQK   vectorized lookup of Q and K //gets the diagonal elements
qK         check, if this is equal to K

Conmutatividad:

CIQ   check if transpose(Q) is equal to Q

Identidad:

}]Km{@RdCBQK
   m       K   map each d in K to:
        CBQ       the list [Q, transpose(Q)]
     @Rd          take the d-th element of each ^
    {             remove duplicates
}]K            check if [K] is in ^

Cierre:

J!-sQK
   sQ    sum(Q) //all elements of Q
  -  K   remove the elements, that also appear in K
 !       ckeck, if the results in an empty list
J        store the result in J

Asociatividad:

&JqF.bsm@[email protected],sQK
               .p,sQK  all permutations of [sum(Q), K] //all 2 ;-)
    .b                 map each pair (N,Y) of ^ to:
       m      N           map each d of N to:
          @Qd                the row Q[d]
        @L   Y               map each element of Y to the corr. element in ^
      s                   unfold this 2-d list
  qF                   check if they result in identically lists
&J                     and J
Jakube
fuente
5

Haskell, 178 171 bytes

import Data.List
f x=[c,c&&and[(m%n)%o==m%(n%o)|m<-b,n<-b,o<-b],x==t,all(elem b)[x,t],b==[i%i|i<-b]]where c=all(l>)(id=<<x);b=[0..l-1];a%b=x!!a!!b;l=length x;t=transpose x

Devuelve una lista con cinco booleanos, que están en orden de cierre, asociatividad, conmutatividad, identidad e idempotencia.

Ejemplo de uso: f [[1, 0, 0],[0, 1, 0],[0, 0, 1]]-> [True,False,True,False,False].

Cómo funciona:

f x=[
  c,                         -- closure (see below)
  c&&and[(m%n)%o==m%(n%o)|   -- assoc: make sure it's closed, then check the
          m<-b,n<-b,o<-b],   --        assoc rule for all possible combinations
  x==t,                      -- comm: x must equal it's transposition
  all(elem b)[x,t],          -- identity: b must be a row and a column
  b==[i%i|i<-b]              -- idemp: element at (i,i) must equal i
  ]
  where                      -- some helper functions
  c=all(l>)(id=<<x);         -- closure: all elements of the input must be < l 
  b=[0..l-1];                -- a list with the numbers from 0 to l-1
  a%b=x!!a!!b;               -- % is an access function for index (a,b)
  l=length x;                -- l is the number of rows of the input matrix
  t=transpose x

Editar @xnor encontró algunos bytes para guardar. ¡Gracias!

nimi
fuente
¿Qué tal c=all(l>)?
xnor
Además, [i%i|i<-b]==b.
xnor
Muy legible para code-golf, ¡bonito!
isaacg
4

CJam, 95 bytes

q~:Ae_A,:Bf<:*'**B3m*{_{A==}*\W%{Az==}*=}%:*'A*A_z='C*B{aB*ee_Wf%+{A==}f*B,2*='1*}%Ae_B)%B,='I*

Imprime una subsecuencia de *AC1I. *es el símbolo de cierre , Aes asociativo , Ces conmutativo , 1es de identidad y Ies idempotente .


La matriz de entrada se lee q~y se almacena en A ( :A).

Cierre

Ae_A,:Bf<:*'**

Si todos los :*elementos ( ) en la matriz ( Ae_) son más pequeños f<que B = tamaño (A) ( A,:B), imprima a *( '**).

Asociatividad

B3m*{_{A==}*\W%{Az==}*=}%:*'A*

Genera todos los triples en el dominio ( B3m*). Imprimimos Asi 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 de A, son iguales ( =).

Conmutatividad

A debe ser igual a su transpuesta: A_z=. Si es así, imprimimos C( 'C=).

Identidad

B{                         }%   For each element X in the domain (0..N-1):
  aB*                           Make N copies.
     ee                         [[0 X] [1 X] ...]
       _Wf%+                    [[0 X] [1 X] ... [X 0] [X 1] ...]
            {A==}f*             [A(0, X) A(1, X) ... A(X, 0) A(X, 1)]
                   B,2*=        This list should equal the domain list repeated twice.
                        '1*     If so, X is an identity: print a 1.

La identidad es necesariamente única, por lo que solo podemos imprimir una 1.

Idempotente

Ae_B)%B,='I*

Comprueba si la diagonal es igual B,. Si es así, imprima un I.

Lynn
fuente
3

Matlab, 226

a=input('');n=size(a,1);v=1:n;c=all(0<=a(:)&a(:)<n);A=c;for i=v;for j=v(1:n*c);for k=v(1:n*c);A=A&a(a(i,j)+1,k)==a(i,a(j,k)+1);end;end;b(i)=all(a(i,:)==v-1 & a(:,i)'==v-1);end;disp([c,A,~norm(a-a'),any(b),all(diag(a)'==v-1)])

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:

  • Cierre : ¿Todas las entradas de matriz en el rango dado?
  • Asociatividad : como siempre, la más difícil de verificar
  • Conmutatividad : ¿es la matriz simétrica?
  • Identidad : ¿Existe un índice k tal que la fila k y la columna k sean exactamente la lista de los índices?
  • Idempotencia : ¿La diagonal corresponde a la lista de índices?

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:

a=input('');
n=size(a,1);
v=1:n;
c=all(0<=a(:)&a(:)<n);               %check for closedness
A=c;
for i=v;
   for j=v(1:n*c); 
      for k=v(1:n*c);
          A=A&a(a(i,j)+1,k)==a(i,a(j,k)+1);   %check for associativity (only if closed)
      end;
   end;
   b(i)=all(a(i,:)==v-1 & a(:,i)'==v-1);      %check for commutativity
end
%closure, assoc, commut, identity, idempotence
disp([c,A,~norm(a-a'),any(b),all(diag(a)'==v-1)]);
falla
fuente
3

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.

q=>q.map((p,i)=>(p.map((v,j)=>(w=q[j][i],v-w?h=C=0:v-j?h=0:0,q[v]?A&=!q[v].some((v,k)=>v-q[i][q[j][k]]):A=K=0),h=1,p[i]-i?P=0:0),h?I=1:0),A=P=K=C=1,I=0)&&[K,A,C,I,P]

Menos golf

f=q=>(
  // A associativity, P idempotence, K closure, C commuativity
  // assumed true until proved false
  A=P=K=C=1, 
  I=0, // Identity assumed false until an identity element is found
  q.map((p,i)=> (
      h=1, // assume current i is identity until proved false
      p[i]-i? P=0 :0, // not idempotent if q[i][i]!=i for any i
      p.map((v,j)=> (
          w=q[j][i], // and v is q[i][j]
          v-w // check if q[j][i] != q[i][j]
          ? h=C=0 // if so, not commutative and i is not identity element too
          : v-j // else, check again for identity
            ? h=0 // i is not identity element if v!=j or w!=j
            : 0,
          q[v] // check if q[i][j] in domain
            ? A&=!q[v].some((v,k)=>v-q[i][q[j][k]]) // loop for associativity check
            : A=K=0 // q[i][j] out of domain, not close and not associative
        )
      ),
      h ? I=1 : 0 // if i is the identity element the identity = true
    )
  ),
  [K,A,C,I,P] // return all as an array
)

Prueba

f=q=>
  q.map((p,i)=>(
    p.map((v,j)=>(
      w=q[j][i],
      v-w?h=C=0:v-j?h=0:0,
      q[v]?A&=!q[v].some((v,k)=>v-q[i][q[j][k]]):A=K=0
    ),h=1,p[i]-i?P=0:0),
    h?I=1:0
  ),A=P=K=C=1,I=0)
  &&[K,A,C,I,P]

// test

console.log=x=>O.textContent+=x+'\n';

T=[
 [
  [[0, 1, 2, 3],
   [1, 1, 2, 3],
   [2, 2, 2, 3],
   [3, 3, 3, 3]]
 ,[1,1,1,1,1]] // has the properties of closure, associativity, commutativity, identity and idempotence.
,[ // exponentiation function on domain n=3:
  [[1, 0, 0],
   [1, 1, 1],
   [1, 2, 4]]
 ,[0,0,0,0,0]] // has none of the above properties.
,[ // addition function on domain n=3:
  [[0, 1, 2],
   [1, 2, 3],
   [2, 3, 4]] 
 ,[0,0,1,1,0]] // has the properties of commutativity and identity.
,[ // K combinator on domain n=3:
  [[0, 0, 0],
   [1, 1, 1],
   [2, 2, 2]]
 ,[1,1,0,0,1]] // has the properties of closure, associativity and idempotence.
,[ // absolute difference function on domain n=3:
  [[0, 1, 2],
   [1, 0, 1],
   [2, 1, 0]]
 ,[1,0,1,1,0]] // has the properties of closure, commutativity and identity.
,[ // average function, rounding towards even, on domain n=3:
  [[0, 0, 1],
   [0, 1, 2],
   [1, 2, 2]]
 ,[1,0,1,1,1]] // has the properties of closure, commutativity, identity and idempotence.
,[ // equality function on domain n=3:
  [[1, 0, 0],
   [0, 1, 0],
   [0, 0, 1]]
 ,[1,0,1,0,0]] // has the properties of closure, commutativity,
]  

T.forEach(t=>{
  F=t[0],X=t[1]+'',R=f(F)+'',console.log(F.join`\n`+'\n'+R+' (expected '+X+') '+(X==R?'OK\n':'Fail\n'))
  })
<pre id=O></pre>

edc65
fuente