2014 dxdy logo

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

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




 
 Внеочередной вопрос про перестановки
Сообщение29.01.2016, 12:20 
Аватара пользователя
Пусть есть у нас некоторое множество перестановок порядка $n$. Есть также некоторый набор перестановок $a_1, a_2, ..., a_k$, назовем его $A$. Существует ли способ узнать иначе чем полным перебором ответ на вопрос: любая ли перестановка порядка $n$ представима в виде произведения перестановок из $A$?

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 12:27 
Аватара пользователя
Вероятно, имеется ввиду следующее: пусть $A,B$ -- некоторые множества перестановок (одного порядка), причем $|A|=k$. Вопрос о способе как узнать, что $B\subset\langle A\rangle$?

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 12:32 
Аватара пользователя
Чтобы сказать, правильно ли Вы переформулировали вопрос, мне бы сначала узнать, что означают угловые скобочки вокруг $A$ :|

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 12:55 
Аватара пользователя
Угловые скобки означают порождение. Так как группа перестановок конечна, то каждый элемент порождает конечную циклическую подгруппу, в которой есть обратный к нему. Так что для конечных групп порождение есть множество конечных произведений самих элементов, а обратные элементы уже предполагаются существующими.

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 12:59 
Аватара пользователя
Для некоторых наборов заведомо известно, что они порождают всю группу перестановок ( например, все транспозиции ). Если заданное множество перестановок содержит или порождает такое, заведомо порождающее $S_n$, множество, то все хорошо.

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 13:57 
Аватара пользователя
Ну да. Пойдет также набор транспозиций, скажем, первого элемента с каждым из остальных; из такого набора получится и набор всех транспозиций, а из него уже. А, скажем, для набора, в котором первый элемент всегда остается на своем месте, можно сразу сказать, что он никоим образом не породит перестановку, в которой первый элемент стоит не на первом месте.

Так вот меня и интересует общий критерий отделения агнцев от козлищ?

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 14:02 
Аватара пользователя
Набор непересекающихся циклов, например, не порождает всего (пардон, не знаю, агнцами Вы это считаете или козлищами). Может быть, каждую перестановку из $A$ разложить в циклы?

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 14:19 
gris в сообщении #1095021 писал(а):
Может быть, каждую перестановку из $A$ разложить в циклы?

Для начала да. Но вот вам пример:
Кубик-рубика, его преобразования вполне себе образуют сабжевую группу. Порождающие элементы известны. Можете ли вы взглянув на эти порождающие элементы сказать, что поворот одного уголка невозможен? (замечу - это четная подстановка)
Доказательство без теории групп мне удалось придумать, а исходя из вида порождающих элементов?

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 14:20 
Аватара пользователя
INGELRII в сообщении #1095019 писал(а):
Так вот меня и интересует общий критерий отделения агнцев от козлищ?

Не уверен, что требуемый критерий можно сформулировать так, чтобы он был бы эффективно проверяемым.

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 14:26 
Вообще, думаю проверка может быть может быть организована как нахождение пути до единицы из каждого проверяемого элмента в графе кэли

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 14:45 
Аватара пользователя
ET
Великие умы мыслят одинаково :D Вопрос изначально и возник из графов Кэли, содержит ли граф все эн-факториал вершин для заданных образующих, или все-таки чуть поменьше.

Иными словами, я так понял, что вопрос либо не решен, либо не решался? И в общем случае ответ даст только перебор, только хардкор?

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 16:24 
Аватара пользователя
INGELRII , компетентный ответ на ваш последний вопрос может дать только крутой алгебраист, лучше всего, если это будет спец. по комбинаторной теории групп. Ждите такого специалиста.

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 16:49 
Аватара пользователя
Можно построить полиномиальный алгоритм, используя технику из статьи M. Furst, J. Hopcroft, E. Luks, "Polynomial time algorithms for permutation groups"

 
 
 
 Re: Внеочередной вопрос про перестановки
Сообщение29.01.2016, 18:30 
Аватара пользователя
Спасибо!

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group