Алгоритм Шрайера — Симса (Glikjnmb Ojgwyjg — Vnbvg)

Алгоритм Шрайера — Симса
Граф Кэли группы $S_{4}$
Назван в честь	Charles Sim и Отто Шрайер
Автор	Чарльз Симс
Предназначение	Определение порядка группы перестановок
Структура данных	Перестановки
Худшее время	$O(n^{3}m+n^{6})$

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

История

Чарльз Симс

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

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

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

Основная идея

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

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

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

Постановка задачи

Симметрической группой $S_{n}$ называют группу, элементами которой являются перестановки элементов некоторого множества $\Omega$. Обычно в качестве такого множества берётся $\Omega =\{1,2,\dots ,n\}$. В таких обозначениях элементы группы можно рассматривать как отображения $\sigma :\Omega \to \Omega$, переводящие множество $\Omega$ в себя, то есть его автоморфизмы. Групповой операцией в таких обозначениях является композиция перестановок, для перестановок $\sigma _{1}$ и $\sigma _{2}$ определяемая как $\sigma =\sigma _{1}\sigma _{2}$, где $\sigma (\omega )=\sigma _{1}(\sigma _{2}(\omega ))$ для $\omega \in \Omega$. Соответственно, единичной перестановкой будет перестановка $\sigma$ такая, что $\sigma (\omega )=\omega$, а обратная перестановка может быть задана как $\sigma ^{-1}(\sigma (\omega ))=\omega$.

Пусть $S=\{g_{1},\dots ,g_{m}\}\subset S_{n}$ — множество перестановок длины $n$. Порождённой подгруппой множества $S$ называют наименьшую по включению подгруппу $\langle S\rangle$, которая содержит $S$ как подмножество или, что эквивалентно, подгруппу всех элементов $S_{n}$, которые могут быть представлены в виде конечного произведения элементов $S$ и обратных к ним. Порядком группы перестановок $S$ называют число элементов в ней $|S|$, а её степенью — мощность множества $|\Omega |$, на котором она действует. В таких обозначениях алгоритм должен уметь:

• Получать порядок ${\textstyle |\langle S\rangle |}$ подгруппы, порождённой данными перестановками,
• По перестановке $g$ проверять, лежит ли она в порождённой подгруппе $\langle S\rangle$,
• Последовательно перечислять элементы порождённой подгруппы без повторений.

Применения

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

Алгоритм

Факторизация группы

Пусть $H$ — подгруппа некоторой конечной группы $G$, через $G/H$ обозначим трансверсаль семейства левых смежных классов $\{gH:g\in G\}$. Любой элемент $g\in G$ может быть единственным образом представлен как $g=th$, где $t\in G/H$ и $h\in H$. Последовательно применяя этот результат к $H$ и её подгруппам, его можно обобщить в следующем виде:

Пусть $G=G^{(0)}\geq G^{(1)}\geq \dots \geq G^{(k)}=\{e\}$ — ряд подгрупп $G$. Тогда любой элемент $g\in G$ может быть единственным образом представлен как $g=g_{1}g_{2}\dots g_{k}$, где $g_{1}\in G^{(0)}/G^{(1)},g_{2}\in G^{(1)}/G^{(2)},\dots ,g_{k}\in G^{(k-1)}/G^{(k)}$.

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

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

• По теореме Лагранжа порядок группы может быть вычислен по формуле ${\textstyle |G|=|G^{(0)}/G^{(1)}|\times |G^{(1)}/G^{(2)}|\times \dots \times |G^{(k-1)}/G^{(k)}|}$,
• Элементы группы можно перечислить, перебирая все возможные представления $g=g_{1}g_{2}\dots g_{k}$.

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

Орбиты и стабилизаторы

Пусть $G$ действует на множестве $\Omega$. Выберем набор элементов ${\textstyle \omega _{1},\dots ,\omega _{k}\in \Omega }$ и построим ряд подгрупп так, чтобы выполнялось ${\textstyle G^{(i)}=G_{\omega _{i}}^{(i-1)}}$, где $G_{\omega }=\{g:g\omega =\omega \}$ — стабилизатор элемента $\omega$. Другими словами, ${\textstyle G^{(i)}}$ — это подгруппа элементов $G$, которые переводят каждый из элементов ${\textstyle \omega _{1},\dots ,\omega _{i}}$ в себя. При таком подходе на каждом следующем шаге часть множества $\Omega$, на которую нетривиально действует очередная подгруппа $G$, будет уменьшаться на один элемент, а порядок подгруппы, с которой ведётся работа, — хотя бы в два раза. Из этого следует, что понадобится $\min(|\Omega |,\log |G|)$ итераций алгоритма, прежде чем будет найдено искомое разбиение.

Для построения смежных классов нужно воспользоваться тем, что существует взаимно-однозначное соответствие (биекция) между элементами орбиты $G\omega$ и левыми смежными классами ${\textstyle G/G_{\omega }}$ стабилизатора ${\textstyle G_{\omega }}$.

Доказательство

По теореме об орбитах и стабилизаторах множество смежных классов $G/G_{\omega }$ и орбита $G\omega$ равномощны. Сопоставим каждому элементу $t\in G/G_{\omega }$ элемент орбиты $t\omega$.

Пусть $t_{1}G_{\omega }=t_{2}G_{\omega }$, тогда и множества $(t_{1}G_{\omega })\omega$ и $(t_{2}G_{\omega })\omega$ совпадают. Но из этого следует, что также совпадают $t_{1}\omega$ и $t_{2}\omega$: $$t_{1}\omega =t_{1}(G_{\omega }\omega )=(t_{1}G_{\omega })\omega =(t_{2}G_{\omega })\omega =t_{2}(G_{\omega }\omega )=t_{2}\omega$$

Каждому смежному классу был поставлен в соответствие ровно один элемент орбиты. В силу того, что смежные классы покрывают всю группу $G$, все сопоставленные элементы различны. Значит, это действительно биекция. ■

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

Проверка принадлежности

Обозначим через ${\overline {u}}$ такой элемент $G/G_{\omega }$, что ${\overline {u}}\omega =u$. Разбиение в ряд стабилизаторов позволит проверять элемент на принадлежность группе:

• Если $g\in G^{(i-1)}$, то найдётся элемент $t_{i}\in G^{(i-1)}/G^{(i)}$ такой, что $g\in t_{i}G^{(i)}$, то есть $t_{i}^{-1}g\in G^{(i)}$,
• В силу биекции между элементами смежного класса и точками орбиты, можно однозначно определить, что $t_{i}={\overline {g(\omega _{i})}}$.

Эти свойства позволяют сделать переход от $G^{(i-1)}$ к $G^{(i)}$, что в итоге приведёт к тому, что текущий элемент должен лежать в $G^{(k)}=\{e\}$. Если это действительно так, то $e=t_{k}^{-1}\dots t_{2}^{-1}t_{1}^{-1}g$, откуда можно выразить $g=t_{1}t_{2}\dots t_{k}$.

Вычисление орбиты

Пусть у группы $G$ есть порождающее множество $S$. Орбиту любого элемента $\alpha$ под действием группы $G=\langle S\rangle$ можно организовать в дерево следующего вида:

• В корне дерева записан некоторый элемент $\alpha \in \Omega$,
• В каждой вершине дерева записан некоторый элемент ${\textstyle \beta \in G(\alpha )}$ из орбиты элемента $\alpha$,
• На ребре, ведущем из вершины с элементом $u$ в вершину с элементом $v$, записан элемент $s\in S$ такой, что $s(u)=v$.

Описанное дерево можно построить обходом в глубину, для этого нужно в каждой вершине $u$ перебирать элемент $s\in S$, пока не окажется, что для $s(u)$ ещё не была выделена вершина. Пример реализации на языке 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)

Здесь функция ${\mathsf {apply}}(a,b)$ возвращает результат применения групповой операции к элементам $a$ и $b$ в качестве первого и второго аргумента, а в ${\mathsf {orbit}}[\alpha ]$ хранится элемент ${\overline {\alpha }}$.

Лемма Шрайера

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

Из леммы Шрайера следует, что стабилизатор $G_{\alpha }$ порождается множеством генераторов Шрайера: $G_{\omega }=\langle \{({\overline {su}})^{-1}s{\overline {u}}\mid u\in G\omega ,s\in S\}\rangle$. Этот результат позволяет по порождающему множеству для $G^{(w-1)}$ и орбите элемента $\omega$ построить порождающее множество для $G^{(\omega )}$. Возможная реализация для функции, возвращающей новое порождающее множество:

# Принимает порождающее множество для 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

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

Просеивание генераторов

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

Пусть $S\subset G$. Тогда можно построить набор $S'$ из не более чем $\vert \Omega \vert ^{2}$ элементов такой, что $\langle S'\rangle =\langle S\rangle$.

Доказательство

Для начала докажем следующую лемму:

Пусть $S\subset G$. Тогда следующие преобразования не меняют $\langle S\rangle$:

1. Замена $s\in S$ на $s^{-1}$
2. Замена $s\in S$ на $st$, где $t\in S$ и $t\neq s$

Доказательство

Пусть после применения одной из этих операций мы получили множество $S'$. Очевидно, что $S'\subset \langle S\rangle$. С другой стороны, эти преобразования могут быть обращены преобразованиями того же типа, поэтому $S\subset \langle S'\rangle$. Значит, $\langle S\rangle =\langle S'\rangle$. ■

С помощью таких преобразований мы можем привести множество $S$ к такому виду, что для любой пары $(i,j)$ в наборе есть не более одного элемента $s$ такого, что: $$s(\omega _{1})=\omega _{1},\ s(\omega _{2})=\omega _{2},\dots ,\ s(\omega _{i-1})=\omega _{i-1},\ s(\omega _{i})=\omega _{j}\neq \omega _{i}$$ Этого можно добиться, добавляя элементы в новое множество $S'$ по одному и действуя аналогично методу Гаусса:

1. Пусть мы хотим добавить в $S'$ новый элемент $s$,
2. Будем идти по $\omega _{1},\dots ,\omega _{n}$ последовательно,
   1. Если $s(\omega _{i})=\omega _{i}$, то переходим к $\omega _{i+1}$,
   2. Если $s(\omega _{i})=\omega _{j}$, то проверяем, встречался ли уже элемент $t$ с такой парой $(i,j)$,
      1. Если встречался, то заменим $s$ на $s^{-1}t$ и перейдём к $\omega _{i+1}$,
      2. Иначе запомним, что $s$ соответствует паре $(i,j)$, и добавим $s$ в текущем виде в $S'$,
3. Если к концу алгоритма мы имеем $s=e$, то игнорируем $s$ и не меняем $S'$.

Данный алгоритм использует только обозначенные выше элементарные операции, поэтому $\langle S'\rangle =\langle S\rangle$. Заметим, что если $s(\omega _{i})=t(\omega _{i})$, то $s^{-1}t(\omega _{i})=\omega _{i}$, поэтому переход к $\omega _{i+1}$ от $s^{-1}t$ в алгоритме является корректным и каждой паре $(i,j)$ действительно соответствует не больше одной перестановки. Учитывая, что всего таких пар не больше $n^{2}$, получаем требуемое утверждение.■

Описанная в доказательстве процедура называется фильтром Симса и работает за $O(|S|\cdot \Omega ^{2})$. Её реализация может выглядеть так:

# Принимает порождающее множество 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

Помимо фильтра Симса для поиска небольшого набора $S'$ может использоваться фильтр Джеррума. В отличие от фильтра Симса, который находит набор из не более, чем $|\Omega |^{2}$ элементов, фильтр Джеррума находит набор из не более чем $|\Omega |$ элементов. В то же время фильтр Джеррума работает за $O(|S|\cdot |\Omega |^{4})$, поэтому в случае алгоритма Шрайера — Симса предпочтительнее использовать именно фильтр Симса.

Алгоритм

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

# Принимает порождающее множество 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. Строится орбита элемента $\omega _{i}$ поиском в глубину,
2. Вычисляются все генераторы Шрайера для $G^{(i+1)}$,
3. Множество генераторов прореживается, чтобы избежать их экспоненциального роста.

На выходе алгоритм вернёт список, элементами которого являются трансверсали смежных классов $G^{(0)}/G^{(1)},G^{(1)}/G^{(2)},\dots ,G^{(k-1)}/G^{(k)}$.

Время работы алгоритма

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

1. Построения дерева орбиты, которое занимает $O(|S|\cdot |\Omega |)$ элементарных операций,
2. Построения генераторов Шрайера, которое занимает $O(|S|\cdot |\Omega |^{2})$ элементарных операций и возвращает $|S|\cdot |\Omega |$ генераторов,
3. Нормализации порождающего множества, которое занимает $O(|S'|\cdot |\Omega |^{2})$ элементарных операций, где $S'$ — множество, полученное на прошлом шаге.

Величина $|\Omega |$ в случае, когда дан набор $S=\{g_{1},\dots ,g_{m}\}\subset S_{n}$, на протяжении алгоритма не меняется и равна $n$. Размер порождающего множество изначально равен $m$, а на каждом последующем шаге не превышает $|\Omega |^{2}=n^{2}$. Таким образом, общее время работы алгоритма в приведённой реализации можно оценить как $O(n^{3}m+n^{6})$.

Вариации алгоритма

Псевдо-линейные версии

Ранее было показано, что алгоритм требует $\min(|\Omega |,\log |G|)$ итераций. В общем случае размер группы может быть порядка $n!$, и в таком случае по формуле Стирлинга $\log |G|\sim n\log n$, что заведомо больше $|\Omega |=n$. Но в некоторых случаях порядок группы небольшой, в связи с чем выгоднее иметь алгоритм, который зависит от $\log |G|$, а не $n$ — например, когда речь идёт о какой-то известной группе, которая задана как группа перестановок.

По теореме Кэли любая конечная группа изоморфна некоторой группе перестановок. Степень такой группы $n$ может быть большой, но для многих групп их порядок $|G|$ таков, что $\log |G|<n$. Например, диэдральная группа $D_{n}$ изоморфна группе перестановок, порождённой циклическим сдвигом $r=(1~~2~~\dots ~~n)$ и отражением $s=(1~~n)(2~~n-1)(3~~n-2)\dots$. То есть степень данной группы равна $n$, а порядок — $2n$, и $\log |G|\sim \log n$. Для таких групп можно рассматривать алгоритмы со временем работы $O(nm\log ^{c}|G|)$, которые называются псевдо-линейными.

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

1. $O(n^{2}\log ^{3}|G|+mn^{2}\log |G|)$ времени и $O(n^{2}\log |G|+mn)$ памяти,
2. $O(n^{3}\log ^{3}|G|+mn^{3}\log |G|)$ времени и $O(n\log ^{2}|G|+mn)$ памяти.

Вероятностная версия

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

Для любой константы $d$ существует алгоритм типа Монте-Карло, который с вероятностью ошибки не больше $n^{-d}$ построит сильное порождающее множество для группы перестановок $G=\langle S\rangle$, используя $O(n\log n\log ^{4}|G|+mn\log |G|)$ времени и $O(n\log |G|+mn)$ памяти.

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