Пусть у нас есть какая-то подгруппа $G$ группы $\S_n$. Эта перестановочная группа $G$ действует на какое-то множество $X$ из $n$ элементов. Будем обозначать элементы этого множества числами, $X = \{1, 2, 3, \dotsc, n-1, n\}$.

Всё действие описывать сложно. А мы хотим компактно хранить действие и эффективно выполнять базовые тестовые операции. Чарльзом Симсом (Charles Sims) в 1960-х годах были предложены таблицы Симса для эффективного представления и анализа перестановочных групп (подгрупп $\S_n$).

Перейдем к более широкой и применимой постановке задачи.

Мы по-прежнему рассматриваем перестановки элементов множества $X = \{1, 2, 3, \dotsc, n-1, n\}$. Для простоты скажем, что группа перестановок элементов множества $X$ совпадает с $\S_n$. Точнее, $\Aut(X) \isom \S_n$, а мы просто поставили тут знак равенства вместо изоморфности.

Возьмём какое-то подмножество перестановок $S \subset \S_n$. Порождённая множеством $S$ группа — группа $\langle S \rangle$, являющейся минимальной по включению подгруппой $\S_n$, содержащей $S$. Мы типа дополнили множество $S$ до группы.

Мы хотим научиться для любого подмножества перестановок $S \subset \S_n$

• Узнать порядок $\bigl| \langle S \rangle \bigr|$
• По перестановке $\sigma$ узнать, принадлежит ли она $\langle S \rangle$
• Создать итератор, выдающий все перестановки из $\langle S \rangle$

Пусть $H$ — подгруппа некоторой конечной группы $G$.

Левая трансверсаль $G \ltrans H$ — множество представителей левых смежных классов $G$ по $H$, то есть

Аналогично, правая трансверсаль $G \rtrans H$ — множество представителей правых смежных классов $G$ по $H$, то есть

Любой элемент $g \in G$ может быть единственным образом представлен как $g = t \cdot h$, где $t \in G \ltrans H$ и $h \in H$. Или как $g = h \cdot t$, где $t \in G \rtrans H$ и $h \in H$, и тоже единственным образом.

Сохраним все трансверсали (левые) в переменные $S_1, S_2, \dotsc, S_k$, то есть $S_j \defeq G^{(j-1)} \ltrans G^{(j)}$ для всех $1 \le j \le k$. Полученный набор трансверсалей называется таблицей Симса группы $G$.

По лемме о представлении заключаем, что таблица Симса $S_1, S_2, \dotsc, S_k$ содержит всю информацию о группе $G$. То есть вместо хранения $|G| = \prod\limits_{j=1}^k |S_j|$ объектов мы храним только $\sum\limits_{j=1}^k |S_j|$.

Узнать порядок $|G|$. По теореме Лагранжа

Перечислить все перестановки из $G$. Из леммы о представлении получаем, что нам достаточно просто перебрать все элементы из трансверсалей. Задача эквивалентна задаче генерации всех кортежей длины $k$, в которых на месте под номером $j$ находится элемент из $S_j$.

Можно представить каждую трансверсаль $S_j$ как список, длина у всех таки списков своя. Получается, можно генерировать числа в смешанной системе счисления с основаниями $|S_1|, |S_2|, \dotsc, |S_k|$, и рассматривать элементы кортежа как номера элементов в соответствующих трансверсалях.