Terapi Kelompok: Identifikasi Kelompok

17

Tulis sebuah program, yang menentukan apakah tabel perkalian magma terbatas yang diberikan mewakili suatu kelompok. Magma adalah himpunan dengan operasi biner yang ditutup, itu artinya

  • untuk semua a, b dalam G, a * b lagi dalam G (Tertutup)

Biarkan (G, *) menjadi magma. (G, *) adalah grup jika

  • untuk semua a, b, c dalam G, (a * b) * c = a * (b * c) (Asosiasi)
  • terdapat elemen e dalam G sedemikian sehingga e * a = a * e = a untuk semua a di G (Keberadaan Elemen netral)
  • untuk semua a dalam G ada ab dalam G sehingga a * b = b * a = e di mana e adalah elemen netral (Existence of Inverse)

Spesifikasi

Input adalah string n ^ 2-1 karakter (satu karakter untuk setiap elemen magma, diizinkan 0-9, az) dan hanya mewakili tabel baca baris demi baris, menghilangkan nama operator. Anda dapat mengasumsikan bahwa input tersebut mewakili magma yang valid (itu berarti setiap elemen appers tepat satu kali di baris tajuk / kolom).

Contoh: Di sini kita memiliki tabel 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

String input akan menjadi 012300123112302230133012. (Atau jika kita menggunakan simbol bisa juga nezdnnezdeezdnzzdneddnez). Perlu diketahui bahwa urutan elemen di baris dan di kolom tidak harus sama, sehingga tabel Z_4 juga bisa terlihat seperti ini:

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

Ini juga berarti bahwa elemen netral tidak harus di kolom pertama atau baris pertama.

Jika itu adalah grup, program harus mengembalikan karakter yang mewakili elemen netral. Jika tidak, ia harus mengembalikan nilai falsy (berbeda dari nilai 0-9 az)

Uji kasus

Non-grup dapat dengan mudah dibangun dengan hanya mengubah satu digit string atau dengan mengubah tabel secara artifisial mendefinisikan operasi yang bertentangan dengan salah satu aksioma grup.

Grup

Sepele

* | x
-----
x | x

xxx

Neutral Element: x

H (grup angka empat)

* | 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

Non-Grup

Loop (Grup yang hilang asosiatif, atau Kelompok-Kuasi dengan elemen netral)

* | 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)

IP-loop (dari 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 (oleh Quincunx, terima kasih!)

Monoids adalah Magma dengan asosiatif dan elemen netral.

* | 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

Monoid lain

(Multiplikasi mod 10, tanpa 5) Kami jelas tidak memiliki invers, dan asosiatif diberikan oleh modulo perkalian 10.

* | 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
cacat
sumber
Kupikir aku akan menambahkan meja lain, jauh lebih besar, hanya untuk bersenang-senang: ideone.com/823aRG
Justin
Hanya untuk bersenang-senang, inilah satu lagi yang sangat besar yang melanggar 0-9a-zaturan: ideone.com/vC0ewt
Justin
Untuk yang tidak tahu apa-apa tentang grup, magma, dan sebagainya, spesifikasinya tidak jelas. Misalnya, apakah operasi bersifat komutatif? (jadi mejanya redundan). Bahkan. posisi netral di baris pertama tidak terkait dengan memiliki urutan yang sama di baris dan kolom: dengan 10101010urutannya sama dan netral di baris dan kolom terakhir
edc65
@edc Groups tidak harus komutatif (grup komutatif disebut abelian). Definisi grup sudah lengkap (itu adalah definisi yang biasa), tambahan apa pun akan memberikan batasan lebih lanjut. Dalam tabel tersebut, perkalian dengan elemen netral biasanya di baris / kolom pertama, dan urutan elemen pada baris / kolom header biasanya sama, tetapi Anda masih bisa menuliskan tabel yang valid tanpa mengikuti konvensi tersebut, yang adalah apa yang ingin saya sertakan di sini.
flawr
1
Saya menghapus beberapa komentar yang tampaknya sudah usang. Tolong beri tahu saya jika ada komentar yang harus dihapus.
Martin Ender

Jawaban:

4

Oktaf, 298 290.270 265 karakter

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: Menangani fungsi yang tidak perlu dihapus.

270: Bagaimanapun, pemeriksaan bahwa e==huntuk e selalu memuaskan e · a = a dan h selalu memuaskan a · h = a tidak diperlukan. Ini tidak mungkin bagi mereka untuk berbeda ( e · h =? ).

Rincian dari penjelasan untuk solusi di bawah ini masih relevan.


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);

Baris pertama

c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')'); hanya menyimpan input ke tabel nxn (dengan karakter nol di tempat tanda operasi), dan kemudian secara leksikografis mengurutkan kolom dan baris, sehingga baris dan kolom menerima urutan yang sama:

+ | 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

Sekarang, saya memetakan kembali "a","b","t","z"ke standar 1, 2, 3, 4, sehingga saya dapat mengindeks tabel secara efisien. Ini dilakukan oleh garis for i=2:b a(a==a(i))=i-1;end;. Ini menghasilkan tabel seperti

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

, tempat kami dapat menghapus baris dan kolom pertama dengan 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

Tabel ini memiliki properti yang diberikan:

  • jika elemen netral e ada, tepat satu ( isscalar) baris dan satu kolom memiliki nilai vektor baris u=[1 2 3 ... number-of-elements]:

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

  • jika setiap elemen a memiliki elemen terbalik a ' , dua hal berlaku: elemen netral e hanya terjadi sekali setiap kolom dan hanya sekali setiap baris ( sum(t=a==e)==1) dan, untuk memenuhi a' · a = a · a ' , kejadian e adalah simetris dalam hal terjemahant==t'

  • a · b dapat diambil dengan t(a,b)pengindeksan sederhana . Kemudian kita periksa asosiatifitas dalam loop yang membosankan:

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

Fungsi mengembalikan elemen netral seperti yang muncul di tabel asli ( e=d(e+1)) atau karakter nil jika tabel tidak menggambarkan grup.

pawel.boczarski
sumber
2
Dilakukan dengan baik dan dijelaskan dengan baik. Seharusnya mengembalikan elemen netral sebagai ganti 1.
edc65
Diperbaiki, sekarang mengembalikan nilai yang tepat.
pawel.boczarski
1
OCTAVE FTW =) Saya tidak yakin tentang dua hal (berasal dari matlab), tetapi mungkin Anda dapat menggunakannya untuk meningkatkan jawaban Anda: Bisakah `a (f (a == a (i))) = i-1` dikurangi untuk a(a==a(i))=i-1? Selain itu Anda mungkin dapat menggunakan (...)^.5bukan sqrt(...).
flawr
@ flawr Terima kasih, keduanya bekerja dalam oktaf (versi 3.8.1).
pawel.boczarski
6

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}

Ini adalah program ruby ​​pertamaku! Ini mendefinisikan fungsi lambda yang dapat kita uji dengan melakukan puts f[gets.chomp]. Saya kembali falseuntuk nilai salah saya. Bagian pertama dari fungsi ini hanya menguraikan input ke dalam peta, kemudian bagian kedua memeriksa kemungkinan.

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
}
Justin
sumber
5
Selamat datang di keajaiban golf di Ruby! ;) niladalah nilai falsy yang lebih pendek dari false. Fungsi dapat didefinisikan sebagai seperti lambda q=->{abort'false'}(jika mereka mengambil parameter, maka gunakan []untuk memanggil mereka sebagai ganti ()). Saya percaya .charsseharusnya sudah memberi Anda sebuah array, jadi tidak perlu .to_a. Jika Anda tidak memerlukan baris baru, $><<satu byte lebih pendek dari putsplus ruang. Hash.newtidak membutuhkan tanda kurung. Hanya itu yang bisa saya lihat untuk saat ini. Teruskan! ;)
Martin Ender
The charshal yang aneh. Apa versi Ruby yang Anda gunakan?
Martin Ender
@ MartinBüttner 1.9.3
Justin
Ah, benar, saya sudah melihat dokumentasi 2.1.5.
Martin Ender
1
Anda bisa menggantinya Math.sqrt(...)dengan ...**0.5. Juga, a if bdapat ditulis ulang: b&&auntuk menghindari dua ruang
Cristian Lupascu
4

JavaScript (ES6) 285 243 278

Jalankan cuplikan untuk menguji (karena ES6 hanya berfungsi di Firefox)

Edit 2 Bug fix. Saya salah dalam menemukan elemen netral, hanya memeriksa satu cara. (Perlu uji kasus yang lebih baik !!!)

Sunting Menggunakan penggabungan string yang lebih sederhana daripada indeks ganda (seperti @Quincunx), saya tidak tahu apa yang saya pikirkan. Juga, cek terbalik yang disederhanakan, masih harus bekerja.

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>

edc65
sumber
2

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

Terkutuklah importitu!

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

Penjelasan

f::String->Stringmemetakan string baik ke e::Char, elemen identitas, atau !.

The whereklausul menciptakan sekelompok variabel dan fungsi, yang saya berkomentar; v::[Int]adalah daftar vertikal elemen, h::[Int]yang horisontal.

%::Char->Char->Char berlaku operasi grup untuk argumennya.

g::[[Int]]adalah tabel grup (untuk penggunaan dereferencing %)

j::Maybe Intberisi indeks identitas vjika ada, jika tidak Nothing, itulah sebabnya isJust jkondisi dalam funtuk identitas.

alexander-brett
sumber
Bisakah Anda jelaskan sedikit apa yang terjadi di sini?
xebtl
Saya telah menambahkan beberapa komentar, tetapi intinya adalah 'terapkan tes ke tabel grup'. Perhatikan bahwa {- -}adalah komentar. Apakah Anda memiliki pertanyaan yang lebih spesifik, atau apakah itu jelas?
alexander-brett
Terima kasih. Saya kira untuk benar-benar memahaminya, saya perlu mempelajari beberapa Haskell terlebih dahulu :-)
xebtl