Внеочередной вопрос про перестановки

[INGELRII]

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

[alcoholist]

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

[INGELRII]

Чтобы сказать, правильно ли Вы переформулировали вопрос, мне бы сначала узнать, что означают угловые скобочки вокруг $A$

[gris]

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

[Brukvalub]

Для некоторых наборов заведомо известно, что они порождают всю группу перестановок ( например, все транспозиции ). Если заданное множество перестановок содержит или порождает такое, заведомо порождающее $S_n$, множество, то все хорошо.

[INGELRII]

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

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

[gris]

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

[ET]

gris в сообщении #1095021 писал(а):

Может быть, каждую перестановку из $A$ разложить в циклы?

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

[Brukvalub]

INGELRII в сообщении #1095019 писал(а):

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

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

[ET]

Вообще, думаю проверка может быть может быть организована как нахождение пути до единицы из каждого проверяемого элмента в графе кэли

[INGELRII]

ET
Великие умы мыслят одинаково Вопрос изначально и возник из графов Кэли, содержит ли граф все эн-факториал вершин для заданных образующих, или все-таки чуть поменьше.

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

[Brukvalub]

INGELRII , компетентный ответ на ваш последний вопрос может дать только крутой алгебраист, лучше всего, если это будет спец. по комбинаторной теории групп. Ждите такого специалиста.

[Xaositect]

Можно построить полиномиальный алгоритм, используя технику из статьи M. Furst, J. Hopcroft, E. Luks, "Polynomial time algorithms for permutation groups"

[INGELRII]

Спасибо!