Muitos tópicos importantes na álgebra abstrata envolvem uma função binária atuando em um conjunto. Várias propriedades de tais funções foram definidas na investigação de tais tópicos.
Seu desafio será determinar se uma determinada função binária em um determinado domínio possui cinco dessas propriedades.
Propriedades
Uma função binária é fechada se todas as saídas possíveis estiverem no domínio.
Uma função binária é associativa se a ordem na qual a função é aplicada a uma série de entradas não afeta o resultado. Ou seja, $é associativo, se (a $ b) $ csempre igual a $ (b $ c). Observe que, já que o valor(a $ b) é usado como entrada, as funções associativas devem ser fechadas.
Uma função binária é comutativa se a troca da ordem das entradas não alterar o resultado. Em outras palavras, se a $ bsempre é igual b $ a.
Uma função binária possui um elemento de identidade se existir algum elemento eno domínio, como a $ e = a = e $ apara todos ano domínio.
Uma função binária é idempotente se aplicá-la a duas entradas idênticas fornecer esse número como saída. Em outras palavras, se for a $ a = apara todos ano domínio.
Entrada
Você receberá uma função na forma de uma matriz, e o domínio da função serão os números 0 ... n-1, onde né o comprimento lateral da matriz.
O valor (a $ b)é codificado na matriz como o elemento th ada linha bth. Se a matriz de entrada for Q, então a $ b=Q[a][b]
Por exemplo, a função de exponenciação ( **em Python) no domínio [0, 1, 2]é codificada como:
[[1, 0, 0]
[1, 1, 1]
[1, 2, 4]]
Os domínios esquerdo e direito são os mesmos, portanto a matriz sempre será quadrada.
Você pode usar qualquer formato de matriz conveniente como entrada, como uma lista de listas, uma única lista em ordem de linhas ou colunas, o objeto de matriz nativa do seu idioma, etc. No entanto, você não pode executar uma função diretamente como entrada.
Para simplificar, todas as entradas da matriz serão inteiras. Você pode assumir que eles se encaixam no tipo inteiro nativo do seu idioma.
Resultado
Você pode indicar quais das propriedades acima estão em qualquer formato que escolher, incluindo uma lista de booleanos, uma sequência com um caractere diferente para cada propriedade etc. No entanto, deve haver uma saída distinta e exclusiva para cada um dos 24 subconjuntos possíveis das propriedades. Essa saída deve ser facilmente legível por humanos.
Exemplos
A função máxima no domínio n = 4:
[[0, 1, 2, 3]
[1, 1, 2, 3]
[2, 2, 2, 3]
[3, 3, 3, 3]]
Essa função possui as propriedades de fechamento, associatividade, comutatividade, identidade e idempotência.
A função de exponenciação no domínio n = 3:
[[1, 0, 0]
[1, 1, 1]
[1, 2, 4]]
Esta função não possui nenhuma das propriedades acima.
A função de adição no domínio n = 3:
[[0, 1, 2]
[1, 2, 3]
[2, 3, 4]]
Essa função tem as propriedades de comutatividade e identidade.
O combinador K no domínio n = 3:
[[0, 0, 0]
[1, 1, 1]
[2, 2, 2]]
Esta função possui as propriedades de fechamento, associatividade e idempotência.
A função de diferença absoluta no domínio n = 3:
[[0, 1, 2]
[1, 0, 1]
[2, 1, 0]]
Esta função tem as propriedades de fechamento, comutatividade e identidade.
A função média, arredondando para par, no domínio n = 3:
[[0, 0, 1]
[0, 1, 2]
[1, 2, 2]]
Esta função possui as propriedades de fechamento, comutatividade, identidade e idempotência.
A função de igualdade no domínio n = 3:
[[1, 0, 0]
[0, 1, 0]
[0, 0, 1]]
Esta função tem as propriedades de fechamento e comutatividade.
Desafio
Isso é código de golfe. Aplicam-se brechas padrão . Menos bytes ganham.
c=all(l>)?[i%i|i<-b]==b.CJam, 95 bytes
Imprime uma subsequência de
*AC1I.*é o símbolo para o fechamento ,Aé para associativo ,Cé para comutativo ,1é para identidade eIé para idempotente .A matriz de entrada é lida
q~e armazenada em A (:A).Fecho
Se todos os
:*elementos ( ) na matriz (Ae_) forem menoresf<que B = tamanho (A) (A,:B), imprima um*('**).Associatividade
Gere todos os triplos no domínio (
B3m*). ImprimimosAse todos eles satisfizerem uma condição ({...}%:*'A*).A condição é que, para alguns triplos
[i j k], dobre à esquerda essa lista com A (_{A==}*) e dobre à esquerda seu reverso[k j i](\W%) com A op ({Az==}*), a versão invertida deAé igual (=).Comutatividade
Um deve ser igual a sua transposta:
A_z=. Nesse caso, imprimimosC('C=).Identidade
A identidade é necessariamente única, portanto, podemos imprimir apenas uma
1.Idempotente
Verifique se a diagonal é igual
B,. Nesse caso, imprima umaI.fonte
Matlab, 226
Uma coisa importante a se notar é que não-fechado implica não-associativo. Muitas dessas propriedades podem ser facilmente verificadas usando algumas propriedades da matriz:
Entrada via notação padrão do Matlab:
[a,b;c,d]ou[[a,b];[c,d]]ou[a b;c d]etcSaída é um vetor de zeros, 1 = verdadeiro, 0 = falso, para cada uma das propriedades na ordem especificada.
Código completo:
fonte
JavaScript (ES6) 165
Uma função anônima que retorna uma matriz com cinco valores 0/1, que estão na ordem Encerramento, Associatividade, Comutatividade, Identidade e Idempotência.
Menos golfe
Teste
fonte