Wprowadzenie
Możesz pominąć tę część, jeśli już wiesz, co to jest grupa cykliczna.
Grupa jest zdefiniowana przez zestaw i asocjacyjną operację binarną $
(to znaczy (a $ b) $ c = a $ (b $ c)
. Istnieje dokładnie jeden element w grupie, e
gdzie a $ e = a = e $ a
dla wszystkich a
w grupie ( tożsamość ). Dla każdego elementu a
w grupie istnieje dokładnie jeden b
taki, że a $ b = e = b $ a
( odwrotnie ) Dla każdego dwóch elementów a, b
w grupie a $ b
jest w grupie ( zamknięcie ).
Możemy pisać a^n
zamiast a$a$a$...$a
.
Cykliczna podgrupa generowana przez dowolny element a
w grupie jest <a> = {e, a, a^2, a^3, a^4, ..., a^(n-1)}
tam, gdzie n
jest kolejność (rozmiar) podgrupy (chyba że podgrupa jest nieskończona).
Grupa jest cykliczna, jeśli może być wygenerowana przez jeden z jej elementów.
Wyzwanie
Biorąc pod uwagę tabelę Cayleya (tabelę produktów) dla skończonej grupy, określ, czy jest ona cykliczna, czy nie.
Przykład
Rzućmy okiem na następujący stół Cayley:
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
(To jest tabela Cayley'a dla Dihedral Group 3, D_3).
Jest to indeksowane 1, więc jeśli chcemy znaleźć wartość 5 $ 3
, patrzymy w piątą kolumnę w trzecim rzędzie (zauważ, że operator niekoniecznie jest przemienny, więc 5 $ 3
niekoniecznie jest równy 3 $ 5
. Widzimy tutaj to 5 $ 3 = 6
(również, że 3 $ 5 = 4
).
Możemy znaleźć <3>
, zaczynając od [3]
, a następnie, gdy lista jest unikalna, dołącz iloczyn ostatniego elementu i generatora (3). Dostajemy [3, 3 $ 3 = 2, 2 $ 3 = 1, 1 $ 3 = 3]
. Zatrzymujemy się tutaj z podgrupą {3, 2, 1}
.
Jeśli obliczyć <1>
poprzez <6>
zobaczysz, że żaden z elementów w grupie wygenerować całą grupę. Zatem ta grupa nie jest cykliczna.
Przypadki testowe
Dane wejściowe będą podawane w postaci macierzy, dane wyjściowe jako wartość decyzji zgodna z prawdą / fałszem.
[[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)
Będziesz mieć pewność, że dane wejściowe są zawsze grupą.
Możesz przyjmować dane wejściowe jako wartości 0-indeksowane.
źródło
[[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]]
)?[1..n]
mogą ukrywać wady w niektórych odpowiedziach.Odpowiedzi:
J , 8 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
1 e.#@C.
fwiwŒCL€1e
6 bajtów w galarecie.Łuska ,
11 109 bajtówNa podstawie 1. Zwraca indeks generatora, jeśli taki istnieje, w przeciwnym razie 0. Wypróbuj online!
Wyjaśnienie
źródło
Galaretka ,
1311 bajtówWypróbuj online!
źródło
JavaScript (ES6), 52 bajty
źródło
Python 2 ,
969197 bajtówWypróbuj online!
źródło
or 1+g
->or-~g
.Galaretka , 15 bajtów
Wypróbuj online!
Pierwszy głupi pomysł, który przyszedł mi do głowy: sprawdź izomorfizm na Z n . (Ten kod to O (n!)…)
źródło
R ,
10197 bajtówSprawdź wszystkie przypadki testowe
To po prostu oblicza
<g>
dla każdego,g \in G
a następnie sprawdza, czyG \subseteq <g>
, a następnie sprawdza, czy którykolwiek z nich jest prawdziwy. Ponieważ jednak zawsze aplikujemy$g
po prawej stronie, replikujemym[g,]
(g
wiersz th), a następnie indeksujemy do tego wiersza z wynikiem zastosowania$g
, gromadząc wyniki zamiast używać zam[g,g$g]
każdym razem, co pozwoliło zaoszczędzić około 4 bajtów.źródło
Clojure, 68 bajtów
źródło
Python 2 , 82 bajty
Wypróbuj online!
Wprowadzono 0-indeksowaną tabelę Cayley; Wyjście prawda / fałsz dla grupy cyklicznej / niecyklicznej.
źródło