Schreiben Sie ein Programm, das festlegt, ob die Multiplikationstabelle des gegebenen endlichen Magmas eine Gruppe darstellt. Ein Magma ist eine Menge mit einer geschlossenen binären Operation, das heißt

• für alle a, b in G ist a * b wieder in G (Geschlossenheit)

Sei (G, *) ein Magma. (G, *) ist eine Gruppe, wenn

• für alle a, b, c in G (a * b) * c = a * (b * c) (Assoziativität)
• es existiert ein Element e in G, so dass e * a = a * e = a für alle a in G (Existenz eines neutralen Elements)
• für alle a in G gibt es ab in G, so dass a * b = b * a = e wobei e das neutrale Element ist (Existenz von Inverse)

Technische Daten

Die Eingabe besteht aus einer Zeichenfolge von n ^ 2-1 Zeichen (ein Zeichen für jedes Element des Magmas, zulässig sind 0-9, az) und stellt nur die zeilenweise gelesene Tabelle dar, wobei der Name des Operators weggelassen wird. Sie können davon ausgehen, dass die Eingabe ein gültiges Magma darstellt (dh, jedes der Elemente wird genau einmal in der Kopfzeile / -spalte eingefügt).

Beispiel: Hier haben wir die Tabelle von Z_4

+ | 0 1 2 3
-----------
0 | 0 1 2 3
1 | 1 2 3 0
2 | 2 3 0 1
3 | 3 0 1 2

Die Eingabezeichenfolge lautet 012300123112302230133012. (Oder wenn wir Symbole verwenden, könnte es auch sein nezdnnezdeezdnzzdneddnez). Beachten Sie, dass die Reihenfolge der Elemente in der Zeile und in der Spalte nicht identisch sein muss, sodass die Tabelle von Z_4 auch so aussehen kann:

+ | 1 3 2 0
-----------
1 | 2 0 3 1
0 | 1 3 2 0
2 | 3 1 0 2
3 | 0 2 1 3

Dies bedeutet auch, dass sich das neutrale Element nicht unbedingt in der ersten Spalte oder ersten Zeile befindet.

Wenn es sich um eine Gruppe handelt, muss das Programm das Zeichen zurückgeben, das das neutrale Element darstellt. Wenn nicht, muss ein falscher (von den Werten 0-9 az verschiedener) Wert zurückgegeben werden

Testfälle

Nicht-Gruppen können leicht konstruiert werden, indem nur eine Ziffer der Zeichenfolge geändert wird oder indem die Tabellen, die eine Operation definieren, die einem der Gruppenaxiome widerspricht, künstlich geändert werden.

Gruppen

Trivial

* | x
-----
x | x

xxx

Neutral Element: x

H (Quaternionsgruppe)

* | p t d k g b n m 
-------------------
m | b d t g k p m n 
p | m k g d t n p b 
n | p t d k g b n m 
b | n g k t d m b p 
t | g m n p b k t d 
d | k n m b p g d t 
k | t b p m n d k g 
g | d p b n m t g k 

ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk

Neutral Element: n

D_4

* | y r s t u v w x
-------------------
u | u x w v y t s r
v | v u x w r y t s
w | w v u x s r y t
x | x w v u t s r y
y | y r s t u v w x
r | r s t y v w x u
s | s t y r w x u v
t | t y r s x u v w


yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw

Neutral Element: y

Z_6 x Z_2

x | 0 1 2 3 5 7 8 9 a b 4 6
---------------------------
0 | 0 1 2 3 5 7 8 9 a b 4 6 
1 | 1 2 3 4 0 8 9 a b 6 5 7 
2 | 2 3 4 5 1 9 a b 6 7 0 8 
7 | 7 8 9 a 6 2 3 4 5 0 b 1 
8 | 8 9 a b 7 3 4 5 0 1 6 2 
9 | 9 a b 6 8 4 5 0 1 2 7 3 
a | a b 6 7 9 5 0 1 2 3 8 4 
b | b 6 7 8 a 0 1 2 3 4 9 5 
3 | 3 4 5 0 2 a b 6 7 8 1 9 
4 | 4 5 0 1 3 b 6 7 8 9 2 a 
5 | 5 0 1 2 4 6 7 8 9 a 3 b 
6 | 6 7 8 9 b 1 2 3 4 5 a 0 

01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0

Neutral Element: 0

A_4

* | i a b c d e f g h j k l
---------------------------
i | i a b c d e f g h j k l
a | a b i e c d g h f l j k
b | b i a d e c h f g k l j
c | c f j i g k a d l b e h
d | d h k b f l i e j a c g
e | e g l a h j b c k i d f
f | f j c k i g d l a h b e
g | g l e j a h c k b f i d
h | h k d l b f e j i g a c
j | j c f g k i l a d e h b
k | k d h f l b j i e c g a
l | l e g h j a k b c d f i

iabcdefghjkliiabcdefghjklaabiecdghfljkbbiadechfgkljccfjigkadlbehddhkbfliejacgeeglahjbckidfffjckigdlahbegglejahckbfidhhkdlbfejigacjjcfgkiladehbkkdhflbjiecgalleghjakbcdfi

Neutral Element: i

Nicht-Gruppen

Eine Schleife (Gruppe ohne Assoziativität oder eine Quasi-Gruppe mit neutralem Element)

* | 1 2 3 4 5
-------------
1 | 1 2 3 4 5 
2 | 2 4 1 5 3 
3 | 3 5 4 2 1 
4 | 4 1 5 3 2 
5 | 5 3 2 1 4

12345112345224153335421441532553214

Neutral Element: 1
(2*2)*3 = 4*3 = 5 != 2 = 2*1 = 2*(2*3)

Eine IP-Schleife (von http://www.quasigroups.eu/contents/download/2008/16_2.pdf )

* | 1 2 3 4 5 6 7
-----------------
1 | 1 2 3 4 5 6 7
2 | 2 3 1 6 7 5 4
3 | 3 1 2 7 6 4 5
4 | 4 7 6 5 1 2 3
5 | 5 6 7 1 4 3 2
6 | 6 4 5 3 2 7 1
7 | 7 5 4 2 3 1 6

123456711234567223167543312764544765123556714326645327177542316

Neutral Element: 1
2*(2*4) = 2*6 = 5 != 7 = 3*4 = (2*2)*4

Monoid (von Quincunx, danke!)

Monoide sind assoziative Magmen und ein neutrales Element.

* | 0 1 2 3
-----------
0 | 0 1 2 3
1 | 1 3 1 3
2 | 2 1 0 3
3 | 3 3 3 3

012300123113132210333333

Neutral Element: 0

Ein weiteres Monoid

(Multiplikation mod 10, ohne die 5) Wir haben offensichtlich keine Inversen, und die Assoziativität ist durch das Multiplikationsmodul 10 gegeben.

* | 1 2 3 4 6 7 8 9
-------------------
1 | 1 2 3 4 6 7 8 9
2 | 2 4 6 8 2 4 6 8
3 | 3 6 9 2 8 1 4 7
4 | 4 8 2 6 4 8 2 6
6 | 6 2 8 4 6 2 8 4
7 | 7 4 1 8 2 9 6 3
8 | 8 6 4 2 8 6 4 2
9 | 9 8 7 6 4 3 2 1

Neutral Element: 1   12346789112346789224682468336928147448264826662846284774182963886428642998764321

Oktave, 298 290 270 265 Zeichen

function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
e=(isscalar(e=find(all(a==u')))&&a(e,:)==u&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);

265: Nicht benötigtes Funktionshandle entfernt.

270: Schließlich war die Prüfung, dass e==hfür e immer e · a = a und h immer a · h = a erfüllt, nicht erforderlich. Dies ist nicht möglich, damit sie unterschiedlich sind ( e · h =? ).

Die Details aus der folgenden Erläuterung zur Lösung sind weiterhin relevant.

290

function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);

Die erste Zeile

c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')'); speichert einfach die Eingabe in der nxn-Tabelle (mit dem Null-Zeichen an der Operationsstelle) und sortiert dann lexikografisch die Spalten und Zeilen, so dass die Zeilen und Spalten die gleiche Reihenfolge erhalten:

+ | z a t b                        + | a b t z
-----------                        -----------
z | t b a z         becomes        a | t a z b
b | z a t b      ============>     b | a b t z
t | a z b t                        t | z t b a
a | b t z a                        z | b z a t

Jetzt ordne ich mich wieder "a","b","t","z"dem Standard zu 1, 2, 3, 4, damit ich die Tabelle effizient indizieren kann. Dies wird von der Leitung erledigt for i=2:b a(a==a(i))=i-1;end;. Es ergibt sich wie Tabelle

0   1   2   3   4
1   3   1   4   2
2   1   2   3   4
3   4   3   2   1
4   2   4   1   3

, wo wir die erste Zeile und Spalte loswerden können mit a=a(2:b,2:b--);u=1:b;:

3  1  4  2
1  2  3  4
4  3  2  1
2  4  1  3

Diese Tabelle hat die angegebenen Eigenschaften:

• Wenn das neutrale Element e existiert, haben genau eine ( isscalar) Zeile und eine Spalte den Wert eines Zeilenvektors u=[1 2 3 ... number-of-elements]:

s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&...

• Wenn jedes Element eines ein umgekehrtes Element a‘ , zwei Dinge zu halten: das neutrale Element e tritt nur einmal jede Spalte und nur einmal je Zeile ( sum(t=a==e)==1) und, zu erfüllen a‚· a = a · a‘ , das Vorkommen von e sind symmetrisch in Bezug auf die Übersetzungt==t'

• a · b kann durch einfache t(a,b)Indizierung abgerufen werden . Dann überprüfen wir die Assoziativität in der langweiligen Schleife:

for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;

Die Funktion gibt das neutrale Element so zurück, wie es in der ursprünglichen Tabelle ( e=d(e+1)) oder als Nullzeichen angezeigt wurde, wenn die Tabelle keine Gruppe beschreibt.

Ruby, 401 ... 272

f=->s{n=(s.size+1)**0.5
w=n.to_i-1
e=s[0,w].split''
s=s[w,n*n]
m={}
w.times{(1..w).each{|i|m[s[0]+e[i-1]]=s[i]}
s=s[n,n*n]}
s=e.find{|a|e.all?{|b|x=m[a+b]
x==m[b+a]&&x==b}}
e.all?{|a|t=!0
e.all?{|b|x=m[a+b]
t||=x==m[b+a]&&x==s
e.all?{|c|m[m[a+b]+c]==m[a+m[b+c]]}}&&t}&&s}

Dies ist mein erstes Rubinprogramm! Dies definiert eine Lambda-Funktion, die wir testen können puts f[gets.chomp]. Ich kehre falsefür meinen falschen Wert zurück. Die erste Hälfte der Funktion parst einfach die Eingabe in eine Karte, dann prüft die zweite Hälfte die Möglichkeiten.

f=->s{
    n=((s.size+1)**0.5).to_i
    w=n-1
    e=s[0,w].split'' # create an array of elements of the potential group
    s=s[w,n*n]
    m={} # this map is what defines our operation
    w.times{
        (1..w).each{               # for each element in the row of the table
            |i|m[s[0]+e[i-1]]=s[i] # put the value into the map
        }
        s=s[n,n*n]
    }
    s=e.find{|a| # s is the identity
        e.all?{|b|
            x=m[a+b]
            x==m[b+a]&&x==b # is a the identity?
        }
    }
    e.all?{|a| # implicit return statement
        t = !0 # t = false
        e.all?{|b| # check for inverses
            x=m[a+b]
            t ||= x==m[b+a]&&x==s # t is now true if b was a's inverse
            e.all?{|c|
                m[m[a+b]+c]==m[a+m[b+c]] # check associativity
            }
        } && t
    }&&s
}

JavaScript (ES6) 285 243 278

Führen Sie den Snippet zum Testen aus (ES6 funktioniert nur unter Firefox)

Edit 2 Bugfix. Ich habe mich geirrt, das neutrale Element zu finden und nur einen Weg zu überprüfen. (Brauche bessere Testfälle !!!)

Bearbeiten Wenn ich einfachere Zeichenfolgenverkettung anstelle von Doppelindex (wie @Quincunx) verwende, weiß ich nicht, was ich gedacht habe. Auch vereinfachte inverse Prüfung sollte es noch funktionieren.

F=t=>(
  e=t.slice(0,d=Math.sqrt(t.length)|0),
  t=t.slice(d).match('.'.repeat(d+1),'g'),
  t.map(r=>{
    for(v=r[i=0],
        j=e.search(v)+1, // column for current row  element
        r!=v+e|t.some(r=>r[j]!=r[0])?0:n=v; // find neutral
        c=r[++i];
       )h[v+e[i-1]]=c
  },h={},n=''),
  e=[...e],!e.some(a=>e.some(b=>(
    h[a+b]==n&&--d, // inverse
    e.some(c=>h[h[a+b]+c]!=h[a+h[b+c]]) // associativity
  )
  ))&&!d&&n
)

input { width: 400px; font-size:10px }

Click on textbox to test - Result : <span id=O></span><br>
<input value='...' onclick='O.innerHTML=F(this.value)'> (?)
<br>Groups<br>
<input value='nezdnnezdeezdnzzdneddnez' onclick='O.innerHTML=F(this.value)'> (n)<br>
<input value='ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk' onclick='O.innerHTML=F(this.value)'> (n)<br>
<input value='yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw' onclick='O.innerHTML=F(this.value)'> (y)<br>
<input value='01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0'onclick='O.innerHTML=F(this.value)'> (0)<br>
Non groups <br>
<input value='12345112345224153335421441532553214' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>
<input value='123456711234567223167543312764544765123556714326645327177542316' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>
<input value='012300123113132210333333' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>

Haskell 391B

import Data.Maybe
import Data.List
o a b=elemIndex b a
l£a=fromJust.o a$l
a§b=[a!!i|i<-b]
f s|isJust j&&and(map(isJust.o h)s)&&and[or[p%q==e|q<-h]&&and[p%(q%r)==(p%q)%r|q<-h,r<-h]|p<-h]=[e]|True="!"where n=floor$(sqrt(fromIntegral$length s+1))-1;h=take n s;g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]];v=s§[n,1+2*n..n+n*n];a%b=g!!(b£v)!!(a£h);j=o g h;e=v!!fromJust j

Verfluche die import!

import Data.Maybe
import Data.List

{- rename elemIndex to save characters -}
o a b=elemIndex b a

{- get the index of l in a -}
l£a=fromJust.o a$l

{- extract a sublist of a with indices b -}
a§b=[a!!i|i<-b]

f s |isJust j {-Identity-}
     &&and (map (isJust.o h) s) {-Closure-}
     &&and[
        or [p%q==e|q<-h] {-Inverse-}
        && and [ p%(q%r)==(p%q)%r | q<-h,r<-h ] {-Associativity-}
     |
        p<-h
     ]=[e]
    |True="!"
    where
    {-size-}    n=floor$(sqrt(fromIntegral$length s+1))-1
    {-horiz-}   h=take n s
    {-table-}   g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]]
    {-vert-}    v=s§[n,1+2*n..n+n*n]
    {-operate-} a%b=g!!(b£v)!!(a£h)
                j=o g h {-index of the first row identical to the top-}
    {-ident-}   e=v!!fromJust j

Erläuterung

f::String->StringOrdnet die Zeichenfolge entweder e::Chardem Identitätselement oder zu !.

Die whereKlausel erstellt eine Reihe von Variablen und Funktionen, die ich kommentiert habe. v::[Int]ist die vertikale Liste der Elemente, h::[Int]die horizontale.

%::Char->Char->Char Wendet die Gruppenoperation auf ihre Argumente an.

g::[[Int]]ist die Gruppentabelle (zur Dereferenzierung mit %)

j::Maybe Intin enthält den Index der Identität , vwenn es vorhanden ist , sonst Nothing, weshalb isJust jin die Bedingung ffür Identität.