Вектор крикуна

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

Обзор

Предположим, что G — конечная группа с порождающей последовательностью $X=\{x_{1},x_{2},...,x_{r}\}$ который действует на конечном множестве $\Omega =\{1,2,...,n\}$. Распространенной задачей в теории вычислительных групп является вычисление орбиты некоторого элемента. $\omega \in \Omega$ под G. В то же время можно записать вектор Шрейера для $\omega$. Затем этот вектор можно использовать для поиска элемента $g\in G$ удовлетворяющий $\omega ^{g}=\alpha$, для любого $\alpha \in \omega ^{G}$. Использование векторов Шрейера для этого требует меньше места для хранения и временных затрат, чем явное сохранение этих g.

Формальное определение

Все используемые здесь переменные определены в обзоре.

Вектор Шрайера для $\omega \in \Omega$ вектор $\mathbf {v} =(v[1],v[2],...,v[n])$ такой, что:

1. $v[\omega ]=-1$
2. Для $\alpha \in \omega ^{G}\setminus \{{\omega }\},v[\alpha ]\in \{1,...,r\}$ (способ, которым $v[\alpha ]$ выбраны, будет пояснено в следующем разделе)
3. $v[\alpha ]=0$ для $\alpha \notin \omega ^{G}$

Использование в алгоритмах

Здесь мы проиллюстрируем с помощью псевдокода использование векторов Шрейера в двух алгоритмах.

• Алгоритм вычисления орбиты ω относительно G и соответствующего вектора Шрейера

Входные данные: ω в Ω , $X=\{x_{1},x_{2},...,x_{r}\}$

для i в {0, 1, …, n }:

set v [ i ] = 0

установить орбиту = { ω }, v [ ω ] = −1

для α на орбите и i в { 1, 2, …, r }:

если $\alpha ^{x_{i}}$ не находится на орбите :

добавить $\alpha ^{x_{i}}$ выходить на орбиту

набор $v[\alpha ^{x_{i}}]=i$

обратная орбита , v

• Алгоритм нахождения g в G такого, что ω ^г = α для некоторого α в Ω , используя v из первого алгоритма

Ввод: v , α , X

если v [ α ] = 0:

вернуть ложь

установите g = e и k = v [ α ] (где e — единичный элемент G )

в то время как k ≠ −1:

набор $g={x_{k}}g,\alpha =\alpha ^{x_{k}^{-1}},k=v[\alpha ]$

вернуть г

Ссылки

• Батлер, Г. (1991), Фундаментальные алгоритмы для групп перестановок , Конспект лекций по информатике, вып. 559, Берлин, Нью-Йорк: Springer-Verlag , ISBN  978-3-540-54955-0 , МР   1225579
• Холт, Дерек Ф. (2005), Справочник по теории вычислительных групп , Лондон: CRC Press , ISBN  978-1-58488-372-2
• Сересс, Акос (2003), Алгоритмы группы перестановок , Cambridge Tracts in Mathematics, vol. 152, Издательство Кембриджского университета , ISBN  978-0-521-66103-4 , МР   1970241