Eigenschaften von Binärfunktionen

14

Bei vielen wichtigen Themen der abstrakten Algebra handelt es sich um eine Binärfunktion, die auf eine Menge einwirkt. Bei der Untersuchung solcher Themen wurde eine Reihe von Eigenschaften solcher Funktionen definiert.

Ihre Herausforderung wird darin bestehen, festzustellen, ob eine gegebene Binärfunktion in einer gegebenen Domäne fünf dieser Eigenschaften besitzt.

Eigenschaften

Schließung

Eine Binärfunktion wird geschlossen, wenn sich jeder mögliche Ausgang in der Domäne befindet.

Assoziativität

Eine Binärfunktion ist assoziativ, wenn die Reihenfolge, in der die Funktion auf eine Reihe von Eingaben angewendet wird, das Ergebnis nicht beeinflusst. Das heißt, $ist assoziativ, wenn (a $ b) $ cimmer gleich a $ (b $ c). Beachten Sie, dass (a $ b)assoziative Funktionen geschlossen werden müssen , da der Wert als Eingabe verwendet wird.

Kommutativität

Eine Binärfunktion ist kommutativ, wenn das Vertauschen der Reihenfolge der Eingänge das Ergebnis nicht ändert. Mit anderen Worten, wenn a $ bimmer gleich b $ a.

Identität

Eine Binärfunktion hat ein Identitätselement, wenn ein der Domäne ein Element vorhanden ist , das a $ e = a = e $ afür alle ain der Domäne gilt.

Idempotenz

Eine Binärfunktion ist idempotent, wenn sie auf zwei identische Eingänge angewendet wird und diese Nummer als Ausgang ergibt. Mit anderen Worten, wenn a $ a = afür allea in der Domäne.

Eingang

Sie erhalten eine Funktion in Form einer Matrix, und die Domäne der Funktion sind die Zahlen 0 ... n-1, in denenn die Seitenlänge der Matrix ist.

Der Wert (a $ b)wird in der Matrix als das ath- bElement der th-Zeile codiert . Wenn die Eingabematrix ist Q, danna $ b =Q[a][b]

Beispielsweise ist die Exponentiationsfunktion ( **in Python) für die Domäne wie [0, 1, 2]folgt codiert:

[[1, 0, 0]
 [1, 1, 1]
 [1, 2, 4]]

Die linke und die rechte Domäne sind identisch, sodass die Matrix immer quadratisch ist.

Sie können ein beliebiges praktisches Matrixformat als Eingabe verwenden, z. B. eine Liste mit Listen, eine einzelne Liste in Zeilen- oder Spaltenreihenfolge, das native Matrixobjekt Ihrer Sprache usw. Sie können jedoch möglicherweise keine Funktion direkt als Eingabe verwenden.

Der Einfachheit halber sind alle Matrixeinträge Ganzzahlen. Sie können davon ausgehen, dass sie in den systemeigenen Integer-Typ Ihrer Sprache passen.

Ausgabe

Sie können angeben, welche der oben genannten Eigenschaften in einem von Ihnen gewählten Format gültig ist, einschließlich einer Liste von Booleschen Werten, einer Zeichenfolge mit einem anderen Zeichen für jede Eigenschaft usw. Für jede der 24 möglichen Teilmengen muss jedoch eine eigene, eindeutige Ausgabe vorliegen der Eigenschaften. Diese Ausgabe muss leicht lesbar sein.

Beispiele

Die maximale Funktion in der Domäne n = 4:

[[0, 1, 2, 3]
 [1, 1, 2, 3]
 [2, 2, 2, 3]
 [3, 3, 3, 3]]

Diese Funktion hat die Eigenschaften Schließung, Assoziativität, Kommutativität, Identität und Idempotenz.

Die Potenzierungsfunktion für die Domäne n = 3:

[[1, 0, 0]
 [1, 1, 1]
 [1, 2, 4]]

Diese Funktion hat keine der oben genannten Eigenschaften.

Die Additionsfunktion auf Domain n = 3:

[[0, 1, 2]
 [1, 2, 3]
 [2, 3, 4]]

Diese Funktion hat die Eigenschaften Kommutativität und Identität.

Der K-Kombinator in Domäne n = 3:

[[0, 0, 0]
 [1, 1, 1]
 [2, 2, 2]]

Diese Funktion hat die Eigenschaften Schließung, Assoziativität und Idempotenz.

Die absolute Differenzfunktion in der Domäne n = 3:

[[0, 1, 2]
 [1, 0, 1]
 [2, 1, 0]]

Diese Funktion hat die Eigenschaften Schließung, Kommutativität und Identität.

Die auf gerade gerundete Durchschnittsfunktion für die Domäne n = 3:

[[0, 0, 1]
 [0, 1, 2]
 [1, 2, 2]]

Diese Funktion hat die Eigenschaften Schließung, Kommutativität, Identität und Idempotenz.

Die Gleichheitsfunktion auf Domain n = 3:

[[1, 0, 0]
 [0, 1, 0]
 [0, 0, 1]]

Diese Funktion hat die Eigenschaften Schließung und Kommutativität.

Herausforderung

Das ist Code Golf. Es gelten Standardlücken . Wenigste Bytes gewinnt.

isaacg
quelle

Antworten:

4

Pyth, 51 Bytes

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

Probieren Sie es online aus: Demonstration oder Test Suite

Dies gibt eine Liste mit 5 Booleschen Werten aus. Sie geben die Eigenschaften in der Reihenfolge an:

[Idempotence, Commutativity, Identity, Closure, Associativity]

Hier ist ein besseres Ausgabeformat: Demonstration oder Test Suite

Erläuterung:

Idempotenz:

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

Kommutativität:

CIQ   check if transpose(Q) is equal to Q

Identität:

}]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 ^

Schließung:

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

Assoziativität:

&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
quelle
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

Gibt eine Liste mit fünf Booleschen Werten zurück, die in der Reihenfolge Abschluss, Assoziativität, Kommutativität, Identität und Idempotenz angegeben sind.

Anwendungsbeispiel: f [[1, 0, 0],[0, 1, 0],[0, 0, 1]]->[True,False,True,False,False] .

Wie es funktioniert:

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

Edit @xnor hat einige Bytes zum Speichern gefunden. Vielen Dank!

nimi
quelle
Wie wäre es c=all(l>)?
24.
Auch [i%i|i<-b]==b.
xnor
Sehr gut lesbar für Code-Golf - schön!
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*

Gibt eine Folge von aus *AC1I. *ist das Symbol für die Schließung , Aist für assoziativ , Cist für kommutativ , 1ist für Identität und Iist für idempotent .


Das Eingabearray wird gelesen q~und in A ( :A) gespeichert .

Schließung

Ae_A,:Bf<:*'**

Wenn alle ( :*) Elemente in der Matrix ( Ae_) kleiner f<als B = Größe (A) ( A,:B) sind, drucken Sie a *('** ).

Assoziativität

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

Generiere alle Tripel in der Domain ( B3m*). Wir drucken, Awenn alle eine Bedingung erfüllen ( {...}%:*'A*).

Die Bedingung ist, dass für ein Dreifaches [i j k], das diese Liste mit A ( _{A==}*) nach links faltet und das Gegenteil [k j i]( \W%) mit A op ( {Az==}*) nach links faltet , die gespiegelte Version von A, gleich ( =) ist.

Kommutativität

A muss seine transponieren gleich: A_z=. Wenn ja, drucken wir C( 'C=).

Identität

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.

Die Identität muss eindeutig sein, daher können wir nur eine drucken 1.

Idempotent

Ae_B)%B,='I*

Überprüfen Sie, ob die Diagonale gleich ist B,. Wenn ja, drucken Sie ein I.

Lynn
quelle
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)])

Es ist wichtig zu bemerken, dass nicht geschlossen nicht assoziativ bedeutet. Viele dieser Eigenschaften können einfach anhand einiger Eigenschaften der Matrix überprüft werden:

  • Abschluss : Alle alle Matrixeinträge im angegebenen Bereich?
  • Assoziativität : Wie immer die am schwierigsten zu überprüfende
  • Kommutativität : Ist die Matrix symmetrisch?
  • Identität : Gibt es einen Index k, bei dem die k-te Zeile und die k-te Spalte genau die Liste der Indizes sind?
  • Idempotenz : Entspricht die Diagonale der Indexliste?

Eingabe über Standard-Matlab-Notation: [a,b;c,d]oder [[a,b];[c,d]]oder [a b;c d]etc

Die Ausgabe ist ein Vektor aus Einsen und Nullen, 1 = wahr, 0 = falsch für jede der Eigenschaften in der angegebenen Reihenfolge.

Vollständiger Code:

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)]);
fehlerhaft
quelle
3

JavaScript (ES6) 165

Eine anonyme Funktion, die ein Array mit fünf 0/1-Werten zurückgibt, und zwar in der Reihenfolge Closure, Associativity, Commutativity, Identity und Idempotence.

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]

Weniger golfen

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
)

Prüfung

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
quelle