группы
В абстрактной алгебре группа - это кортеж , где - множество, а - функция такая, что имеет место следующее:G ∗ G × G → G
Для всех в , .G ( x ∗ y ) ∗ z = x ∗ ( y ∗ z )
Там существует элемент в , что для всех в , .G x G x ∗ e = x
Для каждого в существует такой элемент в , что .G y G x ∗ y = e
Порядок группы определяется как число элементов .G
Для каждого строго положительного целого числа существует хотя бы одна группа порядка . Например, является такой группой, где и .п ( С п , + п ) С п = { 0 , . , , , n - 1 } x + n y = ( x + y )
Изоморфные группы
Пусть и определим как . Тогда и .∗ x ∗ y = ( x × y )1 ∗ 1 = 1 = 2 ∗ 2 1 ∗ 2 = 2 = 2 ∗ 1
Аналогично, и .0 + 2 1 = 1 = 1 + 2 0
Хотя элементы и операции групп и имеют разные имена, группы имеют одинаковую структуру.( C 2 , + 2 )
Две группы и называются изоморфными, если существует биекция такая, что для всех в .( G 2 , ∗ 2 )
Не все группы одного порядка изоморфны. Например, группа Клейна - это группа порядка 4, которая не изоморфна .
задача
Напишите программу или функцию, которая принимает неотрицательное целое число n в качестве входных данных и печатает или возвращает количество неизоморфных групп порядка n .
Контрольные примеры
Input Output
0 0
1 1
2 1
3 1
4 2
5 1
6 2
7 1
8 5
9 2
10 2
11 1
12 5
13 1
14 2
15 1
16 14
17 1
18 5
19 1
20 5
(взято из OEIS A000001 )
Дополнительные правила
Нет ограничений по времени выполнения или использованию памяти.
Встроенные модули, которые упрощают эту задачу, такие как Mathematica
FiniteGroupCount
, не допускаются.Применяются стандартные правила игры в гольф .
источник
monkeys_on_typewriters
встроенная оболочка охватывает все, что не охвачено документированными встроенными функциями.Ответы:
CJam,
189187 байтЭто будет сложно объяснить ... Сложность времени гарантированно будет
O(scary)
.Если вы достаточно смелы, попробуйте это онлайн . На моем дерьмовом ноутбуке я могу получить до 6 с переводчиком Java или 5 с онлайн-переводчиком.
объяснение
У меня нет большого образования по математике (только что закончил среднюю школу, на следующей неделе я начал учиться в университете). Поэтому терпите меня, если я совершаю ошибки, излагаю очевидное или совершаю ужасно неэффективные действия.
Мой подход - грубая сила, хотя я пытался сделать это немного умнее. Основные шаги:
Прежде чем посмотреть, как выполняется каждый шаг, давайте разберемся с некоторым тривиальным кодом:
Следующий алгоритм не работает правильно при n <4 , случаи от 0 до 3 обрабатываются с двойным отрицанием.
Отныне элементы группы будут записываться как {1, a, b, c, ...} , где 1 - элемент идентичности. В реализации CJam соответствующими элементами являются {0, 1, 2, 3, ...} , где 0 - это элемент идентичности.
Начнем с шага 1. Запись всех возможных операторов для группы порядка n эквивалентна генерации всех действительных n × n таблиц Кэли . Первая строка и столбец тривиальны: они оба {1, a, b, c, ...} (слева направо, сверху вниз).
Знание того, что таблица Кэли также является уменьшенным латинским квадратом (из-за свойства отмены), позволяет генерировать возможные таблицы построчно. Начиная со второй строки (индекс 1), мы генерируем все уникальные перестановки для этой строки, сохраняя в первом столбце значение индекса.
Конечно, не все эти перестановки верны: каждая строка и столбец должны содержать все элементы ровно один раз. Блок фильтра используется для этой цели (истинное значение сохраняет перестановку, ложное удаляет ее):
Обратите внимание, что я фильтрую внутри цикла генерации: это делает код немного длиннее (по сравнению с отдельной генерацией и фильтрацией), но значительно повышает производительность. Количество перестановок множества размера n равно n! поэтому более короткое решение потребует много памяти и времени.
Список допустимых таблиц Кейли - отличный шаг к перечислению операторов, но, будучи двумерной структурой, он не может проверить ассоциативность, которая является трехмерным свойством. Поэтому следующим шагом является фильтрация неассоциативных функций.
Уф! Много работы, но теперь мы перечислили все группы порядка n (или лучше, операции над ним - но набор фиксирован, так что это одно и то же). Следующий шаг: найти изоморфизмы. Изоморфизм - это биекция между двумя такими группами, что φ (x ∗ y) = φ (x) ∗ φ (y) . Генерация этих биекций в CJam тривиальна:
Ne!
сделаем это. Как мы можем их проверить? Мое решение начинается с двух копий таблицы Кэли для x ∗ y . На одном экземпляре φ применяется ко всем элементам, не затрагивая порядок строк или столбцов. Это порождает таблицу для φ (x ∗ y) . С другой стороны, элементы остаются без изменений, но строки и столбцы отображаются через φ . То есть строка / столбецх становится строкой / столбцом ф (х) . Это порождает таблицу для φ (x) ∗ φ (y) . Теперь, когда у нас есть две таблицы, мы просто должны сравнить их: если они одинаковы, мы нашли изоморфизм.Конечно, нам также нужно сгенерировать пары групп для проверки изоморфизма. Нам нужны все 2-комбинации групп. Похоже, у CJam нет оператора для комбинаций. Мы можем генерировать их, беря каждую группу и комбинируя ее только с элементами, следующими за ней в списке. Интересный факт: количество 2-комбинаций равно n × (n - 1) / 2 , что также является суммой первых n - 1 натуральных чисел. Такие числа называются треугольными числами: попробуйте алгоритм на бумаге, по одной строке на каждый фиксированный элемент, и вы поймете, почему.
Приведенный выше код фиксирует первый элемент пары, L [X] , и объединяет его с другими группами (назовем каждую из этих Y ). Он передает пару в тестовый блок изоморфизма, который я покажу позже. Блок возвращает список значений Y , для которых L [X] изоморфна Y . Затем L [X] добавляется в этот список. Прежде чем понять, почему списки настроены таким образом, давайте посмотрим на тест на изоморфизм:
Отлично, теперь у нас есть список множеств, таких как [{L [0], Y1, Y2, ...}, {L [1], Y1, ...}, ...] . Идея здесь состоит в том, что по транзитивному свойству, если любые два набора имеют хотя бы один общий элемент, то все группы в этих двух наборах изоморфны. Они могут быть объединены в один набор. Поскольку L [X] никогда не появится в комбинациях, сгенерированных L [X + ...] , после агрегирования каждый набор изоморфизмов будет иметь один уникальный элемент. Итак, чтобы получить количество изоморфизмов, достаточно подсчитать, сколько групп появляется ровно один раз во всех наборах изоморфных групп. Для этого я разворачиваю наборы так, чтобы они выглядели как [L [0], Y1, Y2, ..., L [1], Y1, ...] , сортирую список, чтобы создать кластеры из одной группы, и, наконец, RLE-кодировать это.
Вот и все, ребята.
источник
CJam, 73 байта
Временная сложность приведенного выше кода хуже, чем O (n! N ) .
Ввод n = 4 уже слишком для онлайн-переводчика .
Используя интерпретатор Java , можно ввести n = 5 , если у вас достаточно оперативной памяти и терпения.
Поиск групп
Для группы (G, ∗) порядка n можно выбрать произвольную биекцию φ: G -> C n такую, что φ (e) = 0 .
φ станет изоморфизмом (G, ∗) и ( Cn , ∗ '), если мы определим ∗' как x ∗ 'y = φ (φ -1 (x) ∗ φ -1 (y)) .
Это означает, что достаточно изучить все групповые операторы в C n , так что 0 является нейтральным элементом.
Мы представим групповой оператор ∗ в C n прямоугольным массивом T размерностей n × n , для которого T [x] [y] = x ∗ y .
Чтобы создать такой массив, мы можем начать с выбора перестановки C n для каждой из его n строк.
Таким образом, 0 будет присутствовать во всех строках (но не обязательно во всех столбцах ), означая, что третье условие (существование обратного) будет выполнено, независимо от того, что е может быть.
Мы можем исправить е = 0 , требуя , что первый столбец из Т равна С н . В частности, будет выполнено второе условие (наличие нейтрального элемента).
Чтобы проверить, что T соответствует групповому оператору, все, что осталось сделать, это проверить, что первое условие (ассоциативность) выполняется. Это можно сделать исчерпывающе, проверив, что T [T [x] [y]] [z] == T [x] [T [y] [z]] для всех x, y, z в C n .
Подсчет неизоморфных групп
Приведенный выше метод поиска групп даст некоторые изоморфные группы. Вместо определения того, какие изоморфны, мы генерируем семейство всех изоморфных групп для каждой из них.
Это может быть достигнуто путем итерации по всем биекциям φ: C n -> C n и определения связанного массива Tφ , определенного как Tφ [x] [y] = φ -1 (T [φ (x)] [φ (y) )]) .
Осталось только подсчитать количество разных семей.
Что делает код
источник
Python 2 ,
515507 байтПопробуйте онлайн!
Ссылка на подробную версию .
источник
s
иG
значение? Если нет, вы можете использоватьdef f(k,*s):...f(~-k,j,*s)...
иdef c(k,*G):...c(~-k,s,*G)....
.