Определения

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

группы

В абстрактной алгебре группа - это кортеж (G, ∗) , где G - множество, а ∗ - функция G × G → G такая, что имеет место следующее:

• Замыкание: для всех x, y в G , x ∗ y также есть в G (подразумевается тот факт, что ∗ - функция G × G → G ).

• Ассоциативность: для всех х, у, г в G , (х * у) * г = х * (у * г) .

• Идентичность: существует элемент е в G , что для всех х в G , х * е = х = е * х .

• Обратное: для каждого x в G существует такой элемент y в G , что x ∗ y = e = y ∗ x , где e - единичный элемент, упомянутый в предыдущем пункте.

Конечные группы

Конечная группа представляет собой группу (G, *) , где G конечна, то есть имеет конечное число элементов.

Подгруппы

Подгруппа (Н, *) группы (G, *) такова , что Н представляет собой подмножество G (не обязательно собственное подмножество) и (H, *) также является группой (т.е. удовлетворяет критериям 4 выше).

Примеры

Рассмотрим диэдральную группу D ₃ (G, ∗), где G = {1, A, B, C, D, E} и ∗ определено ниже (такая таблица называется таблицей Кэли ):

∗ | 1 ABCDE
- + ----------------------
1 | 1 ABCDE
A | AB 1 DEC
Б | B 1 AECD
C | CED 1 BA
D | DCEA 1 B
E | EDCBA 1

В этой группе тождество 1 . Кроме того, A и B являются инверсиями друг друга, в то время как 1 , C , D и E являются инверсиями самих себя соответственно (обратное значение 1 равно 1 , обратное значение C равно C , обратное значение D равно D , и обратное E является E ).

Теперь мы можем проверить, что (H, ∗), где H = {1, A, B}, является подгруппой в (G, ∗) . Для закрытия, обратитесь к таблице ниже:

∗ | 1 АБ
- + ----------
1 | 1 АБ
A | AB 1
Б | B 1 A

где все возможные пары элементов в Н при * дают член в H .

Ассоциативность не требует проверки, так как элементы H являются элементами G .

Личность 1 . Это должно быть то же самое с идентичностью группы. Кроме того, личность в группе должна быть уникальной. (Вы можете доказать это?)

Для обратного, проверить , что обратная А это В , который является членом H . Обратный B является , который также является членом H . Инверсия 1 по-прежнему сама по себе, что не требует проверки.

задача

Описание

Для конечной группы (G, ∗) найдите число ее подгрупп.

вход

Для группы (G, *) , вы получите 2D массив размера N × N , где N есть число элементов в G . Предположим, что индекс 0является элементом идентичности. 2D массив будет представлять таблицу умножения. Например, для группы выше вы получите следующий 2D-массив:

[[0, 1, 2, 3, 4, 5],
[1, 2, 0, 4, 5, 3],
[2, 0, 1, 5, 3, 4],
[3, 5, 4, 0, 2, 1],
[4, 3, 5, 1, 0, 2],
[5, 4, 3, 2, 1, 0]]

Например, вы можете видеть, что 3 ∗ 1 = 5, потому что a[3][1] = 5, где a2D-массив выше.

Примечания:

• Вы можете использовать 1-индексированный 2D-массив.
• Строка и столбец для идентификатора могут быть опущены.
• Вы можете использовать другие форматы по своему усмотрению, но они должны быть последовательными. (то есть вы можете захотеть, чтобы последний индекс был тождественным, и т. д.)

Выход

Положительное число, представляющее количество подгрупп в группе.

Например, для указанной выше группы (H, ∗) является подгруппой в (G, ∗) всякий раз, когда H =

• {1}
• {1, A, B}
• {1, C}
• {1, D}
• {1, E}
• {1, A, B, C, D, E}

Следовательно, существует 6 подгрупп, и ваш вывод для этого примера должен быть 6.

Советы

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

счет

Это код-гольф . Ответ с наименьшим количеством байтов.

Mathematica, 62 48 байтов

Count[Subsets@First@#,x_/;Union@@#[[x,x]]==x]-1&

Чистая функция, ожидающая двуиндексный массив с 1 индексом. Countе годы число Subsetsиз Firstстроки входного массива, замкнутых относительно групповой операции. Так как это будет включать пустой набор, мы вычитаем 1. Обратите внимание, что непустое подмножество конечной группы, замкнутое относительно групповой операции, на самом деле является подгруппой (и наоборот, по определению).

Строго говоря, я не проверяю, что подгруппа xзакрыта под групповой операцией, я ограничиваю таблицу умножения подмножеством xи проверяю, что она содержит именно элементы x. Очевидно, это означает, чтоx закрыто относительно групповой операции. И наоборот, любая подгруппа xбудет содержать 1и, таким образом, xбудет подмножеством элементов, появляющихся в таблице ограниченного умножения, и, поскольку xона закрыта для групповой операции, она должна равняться x.

Haskell , 79 байтов

В основном это метод Mathematica от ngenisis. (За исключением того, что я использую 0-индексированные массивы.)

cберет список списков Ints и возвращает целое число.

c g=sum[1|l<-foldr(\r->([id,(r!!0:)]<*>))[[]]g,and[g!!x!!y`elem`l|x<-l,y<-l]]-1

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

Предполагается, что Int номера нумеруются так же, как строки (внешние списки) и столбцы, показывающие их умножение. Таким образом, поскольку 0 является тождеством, первый столбец совпадает с индексами строк. Это позволяет использовать записи первого столбца для построения подмножеств.

Как это устроено

• c это основная функция.
• g это групповой массив в виде списка списков.
• lэто подмножество элементов. Список подмножеств строится следующим образом:
  • foldr(\r->([id,(r!!0:)]<*>))[[]]g складывает функцию по строкам g .
  • rявляется строкой g, чей первый (0-й) элемент извлекается как элемент, который может быть включен ( (r!!0:)) или нет ( id).
  • <*> комбинирует выбор для этой строки со следующими.
• and[g!!x!!y`elem`l|x<-l,y<-l]проверяет каждую пару элементов на наличие lих кратности l.
• sum[1|...]-1 подсчитывает подмножества, которые проходят тест, кроме одного, пустого подмножества.

Желе , 17 16 байтов

1 байт благодаря ETHproductions ( LR → J)

ị³Z⁸ịFḟ
JŒPÇÐḟL’

JŒPÇÐḟL’  main link. one argument (2D array)
J         [1,2,3,...,length of argument]
 ŒP       power set of ^
    Ðḟ    throw away elements that pass the test...
   Ç      in the helper link
      L   length (number of elements that do not pass)
       ’  decrement (the empty set is still closed under
          multiplication, but it is not a subgroup, as
          the identity element does not exist.)

ị³Z⁸ịFḟ   helper link. one argument (1D indexing array)
ị³        elements at required indices of program input (2D array)
  Z       transpose
   ⁸ị     elements at required indices of ^
     F    flatten
      ḟ   remove elements of ^ that are in the argument given
          if the set is closed under multiplication, this will
          result in an empty set, which is considered falsey.

Попробуйте онлайн! (1-индексированных)

Python 2, 297 215 байт

from itertools import*
T=input()
G=T[0]
print sum(all(T[y][x]in g for x,y in product(g,g))*all(any(T[y][x]==G[0]==T[x][y]for y in g)for x in g)*(G[0]in g)for g in chain(*[combinations(G,n)for n in range(len(G)+1)]))

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

Эта программа работает для группы примеров без ==T[x][y], но я все еще уверен, что это необходимо.

Изменить: Теперь предполагается, что элемент идентичности G всегда первым.

Ungolfed:

from itertools import*
T=input()
G=T[0]
def f(x,y):return T[y][x]                                           # function
def C(g):return all(f(x,y)in g for x,y in product(g,g))             # closure
def E(g):return[all(f(x,y)==y for y in g)for x in g]                # identity

a=E(G)
e=any(a)
e=G[a.index(1)]if e else-1                                          # e in G

def I(G):return all(any(f(x,y)==e==f(y,x)for y in G)for x in G)     # inverse

#print e
#print C(G),any(E(G)),I(G)

#for g in chain(*[combinations(G,n)for n in range(len(G)+1)]):      # print all subgroups
#   if C(g)and I(g)and e in g:print g

print sum(C(g)*I(g)*(e in g)for g in chain(*[combinations(G,n)for n in range(len(G)+1)]))

Ungolfed TIO

Элементы отрицательной группы могут быть поддержаны бесплатно, изменив -1на ''.