Apakah siklus grup?

21

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 emana a $ e = a = e $ auntuk semua adalam grup ( identitas ). Untuk setiap elemen adalam grup ada persis satu bsehingga a $ b = e = b $ a( invers ) Untuk setiap dua elemen a, bdalam grup, a $ bada dalam grup ( penutupan ).

Kita bisa menulis a^ndi tempat a$a$a$...$a.

Subkelompok siklik yang dihasilkan oleh setiap elemen adalam grup adalah di <a> = {e, a, a^2, a^3, a^4, ..., a^(n-1)}mana nurutan (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 $ 3tidak 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.

HyperNeutrino
sumber
Apakah input 0-diindeks diperbolehkan? (mis. [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]])?
Neil
@Neil Ya; Saya lupa menentukan. Terima kasih!
HyperNeutrino
5
Anda harus memberi label label elemen grup Anda lebih banyak pada kasus uji. Saat ini baris dan kolom pertama dari tabel selalu [1..n]yang mungkin menyembunyikan kekurangan dalam beberapa jawaban.
Lynn
3
Sepertinya memeriksa apakah grup tersebut cukup untuk lulus ujian. Uji kasus seperti Z_2 * Z_2 akan memperbaikinya.
xnor
2
@HyperNeutrino: Itulah produk langsung dari grup dua elemen dengan dirinya sendiri - juga dikenal sebagai grup empat Klein .
Henning Makholm

Jawaban:

8

J , 8 byte

1:e.#@C.

Cobalah online!

Penjelasan

1:e.#@C.  Input: matrix M
      C.  Convert each row from a permutation to a list of cycles
    #@    Number of cycles in each row
1:        Constant function 1
  e.      Is 1 a member of the cycle lengths?
mil
sumber
Ini juga bisa 1 e.#@C., fwiw
Conor O'Brien
Huh, J beats Jelly‽
Adám
@ Adám Jelly tidak memiliki bawaan untuk mengonversi permutasi antara notasi langsung dan siklus. Saya mungkin bisa menambahkannya sebagai atom nanti, menghasilkan ŒCL€1e6 byte di Jelly.
miles
8

Sekam , 11 10 9 byte

VS≡`ȯU¡!1

Berbasis 1. Mengembalikan indeks generator jika ada, 0 sebaliknya. Cobalah online!

Penjelasan

V          Does any row r of the input satisfy this:
      ¡!    If you iterate indexing into r
   `    1   starting with 1
    ȯU      until a repetition is encountered,
 S≡         the result has the same length as r.
Zgarb
sumber
3

JavaScript (ES6), 52 byte

a=>a.some(b=>!a[new Set(a.map(_=>r=b[r],r=0)).size])
Neil
sumber
3

Python 2 , 96 91 97 byte

lambda x:any(g(r,r[i],i+1)==len(r)for i,r in enumerate(x))
g=lambda x,y,z:y==z or 1+g(x,x[y-1],z)

Cobalah online!

Halvard Hummel
sumber
or 1+g-> or-~g.
Jonathan Frech
2

Jelly , 15 byte

JŒ!ị@€µṂ⁼Jṙ'’$$

Cobalah online!

Gagasan konyol pertama yang muncul di benak: periksa isomorfisma sampai Z n . (Kode ini adalah O (n!) ...)

JŒ!ị@€             Generate all ways to denote this group.
                     (by indexing into every permutation of 1…n)
      µṂ⁼          Is the smallest one equal to this?
         Jṙ'’$$      [[1 2 …  n ]
                      [2 3 …  1 ]    (the group table for Z_n)
                      [… … …  … ]
                      [n 1 … n-1]]
Lynn
sumber
Hah ini pendekatan yang menarik; tidak pernah memikirkan itu! +1
HyperNeutrino
2

R , 101 97 byte

function(m)any(sapply(1:(n=nrow(m)),function(x)all(1:n%in%Reduce(`[`,rep(list(m[x,]),n),x,T,T))))

Verifikasi semua kasus uji

Ini hanya menghitung <g>untuk masing-masing g \in Gdan kemudian menguji jika G \subseteq <g>, lalu memeriksa apakah ada yang benar. Namun, karena kami selalu menerapkan $gdi sebelah kanan, kami mereplikasi m[g,]( gbaris ke - th) dan kemudian mengindeks ke baris itu dengan hasil penerapan $g, mengumpulkan hasil daripada menggunakan m[g,g$g]setiap waktu, yang menghemat sekitar 4 byte.

Giuseppe
sumber
1

Clojure, 68 byte

#(seq(for[l % :when(apply distinct?(take(count l)(iterate l 0)))]l))
NikoNyrh
sumber
1

Python 2 , 82 byte

lambda A:len(A)in[len(set(reduce(lambda a,c:a+[A[a[-1]][n]],A,[n])))for n in A[0]]

Cobalah online!

Tabel Cayley terindeks 0 adalah input; Output Benar / Salah untuk grup siklik / non-siklik.

Chas Brown
sumber