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
sumber
0-9a-z
aturan: ideone.com/vC0ewt10101010
urutannya sama dan netral di baris dan kolom terakhirJawaban:
Oktaf,
298 290.270265 karakter265: Menangani fungsi yang tidak perlu dihapus.
270: Bagaimanapun, pemeriksaan bahwa
e==h
untuk 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:
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:Sekarang, saya memetakan kembali
"a","b","t","z"
ke standar1, 2, 3, 4
, sehingga saya dapat mengindeks tabel secara efisien. Ini dilakukan oleh garisfor i=2:b a(a==a(i))=i-1;end;
. Ini menghasilkan tabel seperti, tempat kami dapat menghapus baris dan kolom pertama dengan
a=a(2:b,2:b--);u=1:b;
:Tabel ini memiliki properti yang diberikan:
isscalar
) baris dan satu kolom memiliki nilai vektor barisu=[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.sumber
a(a==a(i))=i-1
? Selain itu Anda mungkin dapat menggunakan(...)^.5
bukansqrt(...)
.Ruby,
401... 272Ini adalah program ruby pertamaku! Ini mendefinisikan fungsi lambda yang dapat kita uji dengan melakukan
puts f[gets.chomp]
. Saya kembalifalse
untuk nilai salah saya. Bagian pertama dari fungsi ini hanya menguraikan input ke dalam peta, kemudian bagian kedua memeriksa kemungkinan.sumber
nil
adalah nilai falsy yang lebih pendek darifalse
. Fungsi dapat didefinisikan sebagai seperti lambdaq=->{abort'false'}
(jika mereka mengambil parameter, maka gunakan[]
untuk memanggil mereka sebagai ganti()
). Saya percaya.chars
seharusnya sudah memberi Anda sebuah array, jadi tidak perlu.to_a
. Jika Anda tidak memerlukan baris baru,$><<
satu byte lebih pendek dariputs
plus ruang.Hash.new
tidak membutuhkan tanda kurung. Hanya itu yang bisa saya lihat untuk saat ini. Teruskan! ;)chars
hal yang aneh. Apa versi Ruby yang Anda gunakan?Math.sqrt(...)
dengan...**0.5
. Juga,a if b
dapat ditulis ulang:b&&a
untuk menghindari dua ruangJavaScript (ES6) 285
243 278Jalankan 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.
sumber
Haskell 391B
Terkutuklah
import
itu!Penjelasan
f::String->String
memetakan string baik kee::Char
, elemen identitas, atau!
.The
where
klausul 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 Int
berisi indeks identitasv
jika ada, jika tidakNothing
, itulah sebabnyaisJust j
kondisi dalamf
untuk identitas.sumber
{- -}
adalah komentar. Apakah Anda memiliki pertanyaan yang lebih spesifik, atau apakah itu jelas?