Алгоритм Шрайера — Симса

Wikipedia open wikipedia design.

Алгоритм Шрайера — Симса
Symmetric group 4; Cayley graph 4,9.svg
Граф Кэли группы
Назван в честь Чарльз Симс и Отто Шрайер[d]
Автор Чарльз Симс
Предназначение Определение порядка группы перестановок
Структура данных Перестановки
Худшее время

Алгоритм Шрайера — Симса — алгоритм из области вычислительной теории групп, позволяющий после однократного исполнения за линейное время находить порядок группы, порождённой перестановками, проверять принадлежность элемента такой группе и перечислять её элементы. Алгоритм был предложен Чарльзом Симсом в 1970 году для поиска примитивных групп перестановок[1] и основывается на лемме Шрайера о порождении подгрупп[2]. Представление группы перестановок, которое находит алгоритм, аналогично ступенчатому виду матрицы для её пространства строк[3]. Разработанные Симсом методы лежат в основе большинства современных алгоритмов для работы с группами перестановок[4], модификации алгоритма также используются в современных системах компьютерной алгебры, таких как GAP и Magma[en][5]. Одним из наиболее наглядных приложений алгоритма является то, что он может быть использован для решения кубика Рубика[6].

История[править | править код]

Чарльз Симс

Одной из основных задач в теории групп перестановок является поиск групп перестановок заданной степени (то есть минимального числа элементов множества, в группу перестановок которого вкладывается заданная группа перестановок). К 1970 году для степеней от 2 до 11 были найдены все группы перестановок, для степеней от 12 до 15 были найдены все транзитивные группы (то есть подгруппы, действующие на порождающем множестве транзитивно), а для степеней от 16 до 20 были найдены только примитивные группы перестановок[en]. Для поиска примитивных групп большей степени Чарльз Симс разработал программу, которая находит порядок и некоторую структуру в группе перестановок, заданной своим порождающим множеством[1].

Оригинальная программа, упомянутая в работе Симса, была написана для IBM 7040[en] в Ратгерском университете и поддерживала работу с любыми группами, чья степень не превосходила 50[7]. Точная оценка времени работы алгоритма была впервые проведена Фурстом, Хопкрофтом и Лаксом[en] в 1980 году[8]. Время работы было улучшено Джеррумом[en] в 1982[9] и Дональдом Кнутом в 1981 году[10]. В 1980 году была разработана эффективная вероятностная версия алгоритма[11]. Различные вариации алгоритма, включая те, которые используют вектор Шрайера[en] вместо дерева орбиты, были разобраны Шерешем[de] в 2003 году[12][13].

В вычислительной теории групп алгоритмы над группами перестановок — одна из наиболее развитых областей, и даже сегодня большинство из этих алгоритмов основываются на методах, разработанных Симсом[4].

Основная идея[править | править код]

Эффективность вычислений с группой перестановок существенно зависит от того, как она задана в программе[2]. Один из эффективных способов такого задания — выделить ряд её подгрупп и выбрать однозначных представителей смежных классов для каждой подгруппы в этом ряду относительно её предшественника. Предложенный Чарльзом Симсом алгоритм находит ряд подгрупп, в котором каждая следующая группа является стабилизатором предыдущей. Последовательность точек, для которых строятся стабилизаторы, называется базой[en], а множество, содержащее образующие элементы для каждой группы в ряду, — сильным порождающим множеством[en][2].

Алгоритм строит базу и сильное порождающее множество для подгруппы перестановок, заданной своим порождающим множеством, используя лемму Шрайера для нахождения порождающих множеств. Размер получаемых на промежуточных шагах множеств растёт экспоненциально, поэтому были разработаны вариации алгоритма, уменьшающие количество рассматриваемых порождающих элементов[2].

Описанное выше представление разбивает группу в произведение вложенных в неё подмножеств аналогично тому, как ступенчатое представление разбивает векторное пространство в прямую сумму вложенных в него подпространств[3].

Постановка задачи[править | править код]

Симметрической группой называют группу, элементами которой являются перестановки элементов некоторого множества . Обычно в качестве такого множества берётся . В таких обозначениях элементы группы можно рассматривать как отображения , переводящие множество в себя, то есть его автоморфизмы. Соответственно, групповой операцией является композиция перестановок, которая перестановкам и ставит в соответствие перестановку такую, что для всех элементов . Соответственно, единичной перестановкой будет перестановка такая, что , а обратная перестановка может быть задана как [14].

Пусть  — множество перестановок длины . Порождённой подгруппой множества называют наименьшую по включению подгруппу , которая содержит как подмножество или, что эквивалентно, подгруппу всех элементов , которые могут быть представлены в виде конечного произведения элементов и обратных к ним. Порядком группы перестановок называют число элементов в ней , а её степенью — мощность множества , на котором она действует. В таких обозначениях алгоритм должен уметь[7]:

  • Получать порядок подгруппы, порождённой данными перестановками,
  • По перестановке проверять, лежит ли она в порождённой подгруппе ,
  • Последовательно перечислять элементы порождённой подгруппы без повторений.

Применения[править | править код]

Модификации алгоритма реализованы в двух наиболее популярных специализированных на вычислительной теории групп системах компьютерной алгебрыGAP и Magma[en][5]. Инструменты для работы с группами перестановок, включая алгоритмы перечисления смежных классов и алгоритм Шрайера — Симса также представлены в популярных системах более широкого профиля Maple и Mathematica[15]. Изначально алгоритм был разработан для поиска примитивных групп перестановок заданной степени[1], однако впоследствии область его применения многократно выросла — например, с помощью данного алгоритма можно находить решения к заданной конфигурации кубика Рубика, так как его вращения образуют группу[6]. Также алгоритм хорошо показал себя при работе с группами матриц[en][16].

Алгоритм[править | править код]

Факторизация группы[править | править код]

Пусть  — подгруппа некоторой конечной группы , через обозначим трансверсаль семейства левых смежных классов . Любой элемент может быть единственным образом представлен как , где и . Последовательно применяя этот результат к и её подгруппам, его можно обобщить в следующем виде[3][17]:

Пусть ряд подгрупп . Тогда любой элемент может быть единственным образом представлен как , где .

Вычисление порядка и перечисление элементов[править | править код]

Описанное выше представление обладает такими свойствами:

  • По теореме Лагранжа порядок группы может быть вычислен по формуле [3],
  • Элементы группы можно перечислить, перебирая все возможные представления [7].

Чтобы также иметь возможность проверять элементы на принадлежность порождённой подгруппе, нужно рассматривать ряды подгрупп особого вида, а именно — составленные из стабилизаторов[7].

Орбиты и стабилизаторы[править | править код]

Пусть действует на множестве . Выберем набор элементов и построим ряд подгрупп так, чтобы выполнялось , где  — стабилизатор элемента . Другими словами,  — это подгруппа элементов , которые переводят каждый из элементов в себя[7]. При таком подходе на каждом следующем шаге часть множества , на которую нетривиально действует очередная подгруппа , будет уменьшаться на один элемент, а порядок подгруппы, с которой ведётся работа, — хотя бы в два раза. Из этого следует, что понадобится итераций алгоритма, прежде чем будет найдено искомое разбиение[18].

Для построения смежных классов нужно воспользоваться тем, что существует взаимно-однозначное соответствие (биекция) между элементами орбиты и левыми смежными классами стабилизатора [19].

Из доказательства следует, что в качестве представителей смежных классов можно брать элементы, реализующие различные точки орбиты [19].

Проверка принадлежности[править | править код]

Обозначим через такой элемент , что . Разбиение в ряд стабилизаторов позволит проверять элемент на принадлежность группе[7]:

  • Если , то найдётся элемент такой, что , то есть ,
  • В силу биекции между элементами смежного класса и точками орбиты, можно однозначно определить, что .

Эти свойства позволяют сделать переход от к , что в итоге приведёт к тому, что текущий элемент должен лежать в . Если это действительно так, то , откуда можно выразить [7].

Вычисление орбиты[править | править код]

Пусть у группы есть порождающее множество . Орбиту любого элемента под действием группы можно организовать в дерево следующего вида[17]:

  • В корне дерева записан некоторый элемент ,
  • В каждой вершине дерева записан некоторый элемент из орбиты элемента ,
  • На ребре, ведущем из вершины с элементом в вершину с элементом , записан элемент такой, что .

Описанное дерево можно построить обходом в глубину, для этого нужно в каждой вершине перебирать элемент , пока не окажется, что для ещё не была выделена вершина[17]. Пример реализации на языке Python:

# Строит дерево орбиты по заданному элементу w и порождающему множеству S def build_schreier_tree(w, S, orbit):     for g in S:         if g[w] not in orbit:             orbit[g[w]] = apply(g, orbit[w])             build_schreier_tree(g[w], S, orbit) 

Здесь функция возвращает результат применения групповой операции к элементам и в качестве первого и второго аргумента, а в хранится элемент .

Лемма Шрайера[править | править код]

Основная статья: Лемма Шрайера

Из леммы Шрайера следует, что стабилизатор порождается множеством генераторов Шрайера: . Этот результат позволяет по порождающему множеству для и орбите элемента построить порождающее множество для . Возможная реализация для функции, возвращающей новое порождающее множество[20]:

# Принимает порождающее множество для G_{w-1} и орбиту элемента w # Возвращает порождающее множество для G_w def make_gen(S, orbit):     n = len(next(iter(S)))     newS = set()     for s in S:         for u in orbit:             newS.add(reduce(apply, [inverse(orbit[s[u]]), s, orbit[u]]))     return newS 

Этим алгоритм не исчерпывается, так как хотя размер нового порождающего множества и зависит полиномиально от размера орбиты и старого порождающего множества для одного отдельного вызова, в совокупности по всем вызовам данной функции размер порождающего множества растёт экспоненциально[2].

Просеивание генераторов[править | править код]

Чтобы избежать неконтролируемого роста порождающих множеств, необходимо применять процедуру просеивания. Для этого потребуется следующее утверждение[3][20]:

Пусть . Тогда можно построить набор из не более чем элементов такой, что .

Описанная в доказательстве процедура называется фильтром Симса и работает за [21]. Её реализация может выглядеть так:

# Принимает порождающее множество S # Возвращает прореженное порождающее множество S' def normalize(S):     n = len(next(iter(S)))     newS = set()     base = [{} for i in range(n)]     for s in S:         for x in range(0, n):             if s[x] != x:                 if s[x] in base[x]:                     s = apply(inverse(s), base[x][s[x]])                 else:                     base[x][s[x]] = s                     newS.add(s)                     break     return newS 

Помимо фильтра Симса для поиска небольшого набора может использоваться фильтр Джеррума[22]. В отличие от фильтра Симса, который находит набор из не более, чем элементов, фильтр Джеррума находит набор из не более чем элементов. В то же время фильтр Джеррума работает за , поэтому в случае алгоритма Шрайера — Симса предпочтительнее использовать именно фильтр Симса[21].

Алгоритм[править | править код]

Всё вышенаписанное вместе даёт алгоритм, который может быть лаконично реализован следующим образом[20]:

# Принимает порождающее множество S = s1, ..., sk # Возвращает трансверсали смежных классов U1, ..., Uk def schreier_sims(S):     n = len(next(iter(S)))     ans = []     w = 0     while S:         orbit = {}         orbit[w] = tuple(range(n))                  build_schreier_tree(w, S, orbit)         ans += [[orbit[i] for i in orbit]]                  S = normalize(make_gen(S, orbit))         w += 1     return ans 

По шагам его действия имеют следующий смысл:

  1. Строится орбита элемента поиском в глубину,
  2. Вычисляются все генераторы Шрайера для ,
  3. Множество генераторов прореживается, чтобы избежать их экспоненциального роста.

На выходе алгоритм вернёт список, элементами которого являются трансверсали смежных классов .

Время работы алгоритма[править | править код]

Всего алгоритм требует не больше итераций. Каждая итерация состоит из:

  1. Построения дерева орбиты, которое занимает элементарных операций,
  2. Построения генераторов Шрайера, которое занимает элементарных операций и возвращает генераторов,
  3. Нормализации порождающего множества, которое занимает элементарных операций, где  — множество, полученное на прошлом шаге.

Величина в случае, когда дан набор , на протяжении алгоритма не меняется и равна . Размер порождающего множество изначально равен , а на каждом последующем шаге не превышает . Таким образом, общее время работы алгоритма в приведённой реализации можно оценить как [8][12][13].

Вариации алгоритма[править | править код]

Псевдо-линейные версии[править | править код]

Ранее было показано, что алгоритм требует итераций. В общем случае размер группы может быть порядка , и в таком случае по формуле Стирлинга , что заведомо больше . Но в некоторых случаях порядок группы небольшой, в связи с чем выгоднее иметь алгоритм, который зависит от , а не  — например, когда речь идёт о какой-то известной группе, которая задана как группа перестановок[12].

По теореме Кэли любая конечная группа изоморфна некоторой группе перестановок. Степень такой группы может быть большой, но для многих групп их порядок таков, что . Например, диэдральная группа изоморфна группе перестановок, порождённой циклическим сдвигом и отражением . То есть степень данной группы равна , а порядок — , и . Для таких групп можно рассматривать алгоритмы со временем работы , которые называются псевдо-линейными[12].

В попытке приблизить алгоритм к псевдо-линейному и снизить степень , входящую в его время работы, Шереш пришёл к версиям алгоритма, требующим[18]:

  1. времени и памяти,
  2. времени и памяти.

Вероятностная версия[править | править код]

Первая рабочая вероятностная версия алгоритма была разработана Джефри Леоном в 1980 году[11]. Обычно именно её имеют в виду, когда говорят про вероятностный метод Шрайера — Симса. В нём при прореживании генераторов Шрайера данная процедура досрочно прекращалась, если 20 генераторов подряд оказывались разложенными на множители. Шереш показал, что в совокупности с некоторыми оптимизациями эта процедура даёт следующее утверждение[5]:

Для любой константы существует алгоритм типа Монте-Карло, который с вероятностью ошибки не больше построит сильное порождающее множество для группы перестановок , используя времени и памяти.

В современных системах компьютерной алгебры обычно используются модификации данной версии алгоритма с различными эвристиками для ускорения работы программы[5].

Примечания[править | править код]

  1. 1 2 3 Симс, 1970, Введение, с. 169-170
  2. 1 2 3 4 5 Мюррей, 2003, Обзор, с. 1—3
  3. 1 2 3 4 5 Холт, Эйк, О'Брайен, 2005, Базы и сильные порождающие множества. Определения, с. 87—90
  4. 1 2 Шереш, 2003, Введение, с. 1—4
  5. 1 2 3 4 Шереш, 2003, Рандомизированный алгоритм Шрайера — Симса, с. 62—64
  6. 1 2 Брауэр, 2016, Введение, с. 4
  7. 1 2 3 4 5 6 7 Симс, 1970, Компьютерная программа, с. 176-177
  8. 1 2 Фурст, Хопкрофт, Лакс, 1980, Полиномиальные алгоритмы для групп перестановок
  9. Джеррум, 1986, Компактное представление для групп перестановок
  10. Кнут, 1991, Эффективное представление групп перестановок
  11. 1 2 Леон, 1980, Об алгоритме поиска базы и сильного порождающего множества для группы, заданной порождающими перестановками
  12. 1 2 3 4 Шереш, 2003, Обзор вычислительной сложности, с. 48—54
  13. 1 2 Холт, Эйк, О'Брайен, 2005, Базы и сильные порождающие множества. Вычислительная сложность и особенности реализации, с. 93—94
  14. Журавлёв, Флёров, Вялый, 2019, Перестановки, с. 31—36
  15. Холт, Эйк, О'Брайен, 2005, Исторический обзор вычислительной теории групп, с. 1—7
  16. Мюррей, О'Брайен, 1995, Выбор базовых точек для алгоритма Шрайера — Симса над группами матриц
  17. 1 2 3 Мюррей, 2003, Основные понятия, с. 9—24
  18. 1 2 Шереш, 2003, Алгоритм Шрайера — Симса, с. 59—62
  19. 1 2 Журавлёв, Флёров, Вялый, 2019, Орбиты и стабилизаторы, с. 140-145
  20. 1 2 3 Мюррей, 2003, Алгоритм Шрайера — Симса, с. 25—33
  21. 1 2 Vipul Naik. Sims filter (англ.). Groupprops, The Group Properties Wiki. Дата обращения 23 сентября 2019.
  22. Vipul Naik. Jerrum's filter (англ.). Groupprops, The Group Properties Wiki. Дата обращения 19 сентября 2023.

Литература[править | править код]



This page is based on a Wikipedia article written by contributors (read/edit).
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

Destek