Вопрос о подгруппах

[arseniiv]

Есть какой-нибудь хороший способ/алгоритм кроме ужасного перебора чтобы найти все подгруппы (мне нужно группы $S_n$, если это даст какой-то "хороший" частный случай ), содержащие заданные элементы.
Например, если указать единичный, должно получиться множество всех подгрупп.

[ИСН]

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

[arseniiv]

А сколько подгрупп у $S_8$, например? (Забыл номер последовательности в OEIS.)

[arseniiv]

Ну тогда такой алгоритм, чтобы выдавал случайную подгруппу. Хотя тут уже думать не надо. Надо добавить к нашим элементам случайное количество случайных и получить образуемую элементами подгруппу, перемножая их по-всякому (хотя тут как раз неясно, когда удостоверяться, что все возможные различные произведения получены). Точнее, мне нужно потом найти какие-нибудь порождающие элементы полученной группы. Не знаю как.

[maxal]

В OEIS:
A005432
A000638
Точных значений не так много известно.

-- Sun Dec 27, 2009 10:57:09 --

arseniiv
Посмотрите на GAP или SAGE - там подобные алгоритмы должны быть реализованы:
http://www.gap-system.org/Manuals/doc/h ... HAP041.htm
http://www.sagemath.org/doc/reference/s ... group.html

[arseniiv]

GAP я знаю, хорошая программа. Но мне надо будет реализовать в своей, не хотелось бы за собой GAP таскать...
Не слишком большие значения в последовательностях для прямого перебора...
Хотя я думаю, полез куда-то не туда. В моей задаче вовсе не обязательно строить вообще никаких групп. Вот она: хочу сделать простую игру, где будут какие-нибудь кнопки или что-то им подобное, каждая будет умножать внутреннее состояние на какую-нибудь свою перестановку, и надо донажимать до какого-нибудь состояния, например, тождественной перестановки (отдельные "свойства" состояния будут видны, так что можно будет потом догадаться, что как нажать). Для каждого уровня будет генерироваться определённое число этих перестановочных кнопок, всё больше и больше, чтобы потом совершенно запутать угадывающего. С чего мне взбрело в голову, что нужно знать всю ими образуемую подгруппу, не знаю... Видимо, чего-то хотел от этой группы, но забыл к вечеру...

[maxal]

arseniiv
Все равно почитайте документацию к GAP - там, как правило, рассказано каким алгоритмами что считается и даны ссылки на литературу.

[arseniiv]

Аааа

[Shtirlitz]

Есть книжка. Автор Sims. Computations with finitely presented groups.