Является ли группа циклической?

21

Вступление

Вы можете пропустить эту часть, если вы уже знаете, что такое циклическая группа.

Группа определяется множеством и ассоциативной бинарной операцией $(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-индексированные значения.

HyperNeutrino
источник
Разрешен ли 0-индексированный ввод? (например [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]])?
Нил
@ Нейл Да; Я забыл уточнить. Благодарность!
HyperNeutrino
5
В тестовых примерах вы должны предварительно пометить метки элементов вашей группы. Прямо сейчас первая строка и столбец таблицы всегда [1..n]могут скрывать недостатки в некоторых ответах.
Линн
3
Похоже, проверки достаточности абелевой группы достаточно для прохождения тестовых случаев. Тестовые случаи, подобные Z_2 * Z_2, исправят это.
xnor
2
@HyperNeutrino: Это прямое произведение двухэлементной группы на себя - также известной как четырехгруппа Кляйна .
Хеннинг

Ответы:

8

J , 8 байт

1:e.#@C.

Попробуйте онлайн!

объяснение

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?
миль
источник
Это также может быть 1 e.#@C., fwiw
Конор О'Брайен
Да, J побеждает Jelly‽
Адам
@ Adám Jelly не имеет встроенной функции для преобразования перестановок между прямой и циклической нотацией. Я мог бы, вероятно, добавить их в виде атомов позже, получив ŒCL€1e6 байт в желе.
миль
8

Шелуха , 11 10 9 байт

VS≡`ȯU¡!1

1 на основе. Возвращает индекс генератора, если он существует, 0 в противном случае. Попробуйте онлайн!

объяснение

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
источник
3

JavaScript (ES6), 52 байта

a=>a.some(b=>!a[new Set(a.map(_=>r=b[r],r=0)).size])
Нил
источник
2

Желе , 15 байт

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

Попробуйте онлайн!

Первая глупая идея, которая пришла в голову: проверить на изоморфизм Z n . (Этот код 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]]
Линн
источник
Да, это интересный подход; никогда не думал об этом! +1
HyperNeutrino
2

R , 101 97 байт

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

Проверьте все контрольные примеры

Это просто вычисляет <g>для каждого, g \in Gа затем проверяет, если G \subseteq <g>, затем проверяет, являются ли какие-либо из них истинными. Однако, поскольку мы всегда применяем $gсправа, мы копируем m[g,]( gth-я строка) и затем индексируем в эту строку результат применения $g, накапливая результаты, а не используя m[g,g$g]каждый раз, что экономит около 4 байтов.

Giuseppe
источник
1

Clojure, 68 байт

#(seq(for[l % :when(apply distinct?(take(count l)(iterate l 0)))]l))
NikoNyrh
источник
1

Python 2 , 82 байта

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

Попробуйте онлайн!

0-индексированная таблица Кейли является входной; True / False выход для циклической / нециклической группы.

Час Браун
источник