Вступление
Вы можете пропустить эту часть, если вы уже знаете, что такое циклическая группа.
Группа определяется множеством и ассоциативной бинарной операцией $
(т (a $ b) $ c = a $ (b $ c)
. Е. В группе существует ровно один элемент, e
где a $ e = a = e $ a
для всех a
в группе ( идентичность ). Для каждого элемента a
в группе существует ровно один b
такой, что a $ b = e = b $ a
( обратный ) За каждые два элемента a, b
в группе, a $ b
находится в группе ( замыкание ).
Мы можем написать a^n
вместо a$a$a$...$a
.
Циклическая подгруппа, генерируемая любым элементом a
в группе, - это <a> = {e, a, a^2, a^3, a^4, ..., a^(n-1)}
где n
порядок (размер) подгруппы (если только подгруппа не бесконечна).
Группа является циклической, если она может быть сгенерирована одним из ее элементов.
Вызов
Учитывая таблицу Кейли (таблицу продуктов) для конечной группы, определите, является ли она циклической.
пример
Давайте посмотрим на следующую таблицу Кейли:
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
(Это таблица Кэли для диэдральной группы 3, D_3).
Это индексируется 1, поэтому, если мы хотим найти значение 5 $ 3
, мы смотрим в пятом столбце в третьей строке (обратите внимание, что оператор не обязательно является коммутативным, поэтому 5 $ 3
не обязательно равен 3 $ 5
. Мы видим здесь, что 5 $ 3 = 6
(также это 3 $ 5 = 4
).
Мы можем найти <3>
, начав с [3]
, а затем, пока список уникален, добавляем произведение последнего элемента и генератора (3). Мы получаем [3, 3 $ 3 = 2, 2 $ 3 = 1, 1 $ 3 = 3]
. Мы останавливаемся здесь с подгруппой {3, 2, 1}
.
Если вы <1>
выполните вычисления, <6>
вы увидите, что ни один из элементов в группе не генерирует всю группу. Таким образом, эта группа не является циклической.
Тестовые случаи
Входные данные будут представлены в виде матрицы, а выходные данные будут представлены в качестве истинного / ложного значения решения.
[[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)
Вам будет гарантировано, что вход всегда является группой.
Вы можете принять ввод как 0-индексированные значения.
источник
[[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]]
)?[1..n]
могут скрывать недостатки в некоторых ответах.Ответы:
J , 8 байт
Попробуйте онлайн!
объяснение
источник
1 e.#@C.
, fwiwŒCL€1e
6 байт в желе.Шелуха ,
11 109 байт1 на основе. Возвращает индекс генератора, если он существует, 0 в противном случае. Попробуйте онлайн!
объяснение
источник
Желе ,
1311 байтПопробуйте онлайн!
источник
JavaScript (ES6), 52 байта
источник
Python 2 ,
969197 байтПопробуйте онлайн!
источник
or 1+g
->or-~g
.Желе , 15 байт
Попробуйте онлайн!
Первая глупая идея, которая пришла в голову: проверить на изоморфизм Z n . (Этот код O (n!)…)
источник
R ,
10197 байтПроверьте все контрольные примеры
Это просто вычисляет
<g>
для каждого,g \in G
а затем проверяет, еслиG \subseteq <g>
, затем проверяет, являются ли какие-либо из них истинными. Однако, поскольку мы всегда применяем$g
справа, мы копируемm[g,]
(g
th-я строка) и затем индексируем в эту строку результат применения$g
, накапливая результаты, а не используяm[g,g$g]
каждый раз, что экономит около 4 байтов.источник
Clojure, 68 байт
источник
Python 2 , 82 байта
Попробуйте онлайн!
0-индексированная таблица Кейли является входной; True / False выход для циклической / нециклической группы.
источник