2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Вопрос о подгруппах
Сообщение27.12.2009, 13:23 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Вопрос о подгруппах
Сообщение27.12.2009, 14:22 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос о подгруппах
Сообщение27.12.2009, 14:47 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Вопрос о подгруппах
Сообщение27.12.2009, 16:32 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Вопрос о подгруппах
Сообщение27.12.2009, 18:54 
Модератор
Аватара пользователя


11/01/06
5710
В 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

 Профиль  
                  
 
 Re: Вопрос о подгруппах
Сообщение27.12.2009, 19:16 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Вопрос о подгруппах
Сообщение27.12.2009, 19:23 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос о подгруппах
Сообщение27.12.2009, 19:51 
Заслуженный участник


27/04/09
28128
Аааа

 Профиль  
                  
 
 Re: Вопрос о подгруппах
Сообщение07.01.2011, 20:05 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group