pengantar
Anda dapat melewati bagian ini jika Anda sudah tahu apa itu grup siklik.
Grup didefinisikan oleh set dan operasi biner asosiatif $
(yaitu (a $ b) $ c = a $ (b $ c)
,. Ada persis satu elemen dalam grup di e
mana a $ e = a = e $ a
untuk semua a
dalam grup ( identitas ). Untuk setiap elemen a
dalam grup ada persis satu b
sehingga a $ b = e = b $ a
( invers ) Untuk setiap dua elemen a, b
dalam grup, a $ b
ada dalam grup ( penutupan ).
Kita bisa menulis a^n
di tempat a$a$a$...$a
.
Subkelompok siklik yang dihasilkan oleh setiap elemen a
dalam grup adalah di <a> = {e, a, a^2, a^3, a^4, ..., a^(n-1)}
mana n
urutan (ukuran) dari subkelompok (kecuali jika subkelompok tersebut tidak terbatas).
Grup adalah siklik jika dapat dihasilkan oleh salah satu elemennya.
Tantangan
Mengingat tabel Cayley (tabel produk) untuk grup terbatas, tentukan apakah itu siklik atau tidak.
Contoh
Mari kita lihat tabel Cayley berikut:
1 2 3 4 5 6
2 3 1 6 4 5
3 1 2 5 6 4
4 5 6 1 2 3
5 6 4 3 1 2
6 4 5 2 3 1
(Ini adalah tabel Cayley untuk Dihedral Group 3, D_3).
Ini adalah 1-diindeks, jadi jika kita ingin menemukan nilai 5 $ 3
, kita melihat di kolom kelima pada baris ketiga (perhatikan bahwa operator tidak selalu komutatif, jadi 5 $ 3
tidak harus sama dengan 3 $ 5
. Kita lihat di sini bahwa 5 $ 3 = 6
(juga yang 3 $ 5 = 4
).
Kita dapat menemukannya <3>
dengan mulai dengan [3]
, dan kemudian sementara daftar itu unik, tambahkan produk dari elemen terakhir dan generator (3). Kami mendapatkan [3, 3 $ 3 = 2, 2 $ 3 = 1, 1 $ 3 = 3]
. Kami berhenti di sini dengan subkelompok {3, 2, 1}
.
Jika Anda menghitung <1>
melalui <6>
Anda akan melihat bahwa tidak ada elemen dalam grup yang menghasilkan seluruh grup. Dengan demikian, grup ini bukan siklik.
Uji Kasus
Input akan diberikan sebagai matriks, output sebagai nilai keputusan yang benar / salah.
[[1,2,3,4,5,6],[2,3,1,6,4,5],[3,1,2,5,6,4],[4,5,6,1,2,3],[5,6,4,3,1,2],[6,4,5,2,3,1]] -> False (D_3)
[[1]] -> True ({e})
[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]] -> True ({1, i, -1, -i})
[[3,2,4,1],[2,4,1,3],[4,1,3,2],[1,3,2,4]] -> True ({-1, i, -i, 1})
[[1,2],[2,1]] -> True ({e, a} with a^-1=a)
[[1,2,3,4,5,6,7,8],[2,3,4,1,6,7,8,5],[3,4,1,2,7,8,5,6],[4,1,2,3,8,5,6,7],[5,8,7,6,1,4,3,2],[6,5,8,7,2,1,4,3],[7,6,5,8,3,2,1,4],[8,7,6,5,4,3,2,1]] -> False (D_4)
[[1,2,3,4,5,6],[2,1,4,3,6,5],[3,4,5,6,1,2],[4,3,6,5,2,1],[5,6,1,2,3,4],[6,5,2,1,4,3]] -> True (product of cyclic subgroups of order 2 and 3, thanks to Zgarb)
[[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,1,2]] -> False (Abelian but not cyclic; thanks to xnor)
Anda akan dijamin bahwa input selalu berupa grup.
Anda dapat mengambil input sebagai nilai yang diindeks 0.
sumber
[[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]]
)?[1..n]
yang mungkin menyembunyikan kekurangan dalam beberapa jawaban.Jawaban:
J , 8 byte
Cobalah online!
Penjelasan
sumber
1 e.#@C.
, fwiwŒCL€1e
6 byte di Jelly.Sekam ,
11 109 byteBerbasis 1. Mengembalikan indeks generator jika ada, 0 sebaliknya. Cobalah online!
Penjelasan
sumber
Jelly ,
1311 byteCobalah online!
sumber
JavaScript (ES6), 52 byte
sumber
Python 2 ,
969197 byteCobalah online!
sumber
or 1+g
->or-~g
.Jelly , 15 byte
Cobalah online!
Gagasan konyol pertama yang muncul di benak: periksa isomorfisma sampai Z n . (Kode ini adalah O (n!) ...)
sumber
R ,
10197 byteVerifikasi semua kasus uji
Ini hanya menghitung
<g>
untuk masing-masingg \in G
dan kemudian menguji jikaG \subseteq <g>
, lalu memeriksa apakah ada yang benar. Namun, karena kami selalu menerapkan$g
di sebelah kanan, kami mereplikasim[g,]
(g
baris ke - th) dan kemudian mengindeks ke baris itu dengan hasil penerapan$g
, mengumpulkan hasil daripada menggunakanm[g,g$g]
setiap waktu, yang menghemat sekitar 4 byte.sumber
Clojure, 68 byte
sumber
Python 2 , 82 byte
Cobalah online!
Tabel Cayley terindeks 0 adalah input; Output Benar / Salah untuk grup siklik / non-siklik.
sumber