Алгоритм факторизации подстановки

[arseniiv]

Есть ли алгоритм (перебором слишком долго) факторизации данной подстановки $P$ с помощью множества подстановок $\{P_1 , P_2 , \ldots , P_n\}$. Известно также, что оно является системой образующих группы, в которую входит $P$, т.е. разложение на множители существует.
Или какой-нибудь мат. пакет, который мог бы быстро вычислить разложение.

[Профессор Снэйп]

Если $P_1, \ldots, P_n$ --- все транспозиции, то, конечно, есть. А для произвольных $P_1, \ldots, P_n$ --- не знаю.

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

[arseniiv]

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

-- Чт авг 06, 2009 17:37:51 --

Даже "облегчал" перебор, исходя из свойств данных перестановок (их 4), всё равно не выходило...

-- Чт авг 06, 2009 18:12:16 --

Вот что известно:
$P = \left( {4,6,3,2,1,5,10,9,11,8,7} \right)$
$P_1 = \left( {6,1,2,3,4,5,7,8,9,10,11} \right)$
$P_2 = \left( {1,10,9,8,5,6,7,4,3,2,11} \right)$
$P_3 = \left( {9,8,7,4,5,6,3,2,1,10,11} \right)$
$P_4 = \left( {7,11,3,4,5,8,1,6,9,10,2} \right)$
Порядки порождаемых циклических групп (я это учитывал и не умножал $P_2$ на $P_2$ и пр.):
$P_1^6 = P_2^2 = P_3^2 = P_4^2 = e$

-- Чт авг 06, 2009 20:03:52 --

Ещё, по моим подсчётам, произведение должно быть не более чем из 12 множителей

[maxal]

arseniiv в сообщении #233318 писал(а):

Есть ли алгоритм (перебором слишком долго) факторизации данной подстановки $P$ с помощью множества подстановок $\{P_1 , P_2 , \ldots , P_n\}$. Известно также, что оно является системой образующих группы, в которую входит $P$, т.е. разложение на множители существует.
Или какой-нибудь мат. пакет, который мог бы быстро вычислить разложение.

GAP такое умеет:
http://www.gap-system.org/Manuals/doc/h ... tm#SECT005

[arseniiv]

Спасибо, maxal! Сейчас установлю и разложу себе на здоровье.

[Профессор Снэйп]

arseniiv в сообщении #233331 писал(а):

Вот что известно:
$P = \left( {4,6,3,2,1,5,10,9,11,8,7} \right)$
$P_1 = \left( {6,1,2,3,4,5,7,8,9,10,11} \right)$
$P_2 = \left( {1,10,9,8,5,6,7,4,3,2,11} \right)$
$P_3 = \left( {9,8,7,4,5,6,3,2,1,10,11} \right)$
$P_4 = \left( {7,11,3,4,5,8,1,6,9,10,2} \right)$
Порядки порождаемых циклических групп (я это учитывал и не умножал $P_2$ на $P_2$ и пр.):
$P_1^6 = P_2^2 = P_3^2 = P_4^2 = e$

Чёта я не понял. Как это $P_2^2 = e$, если $P_2$ --- цикл длины $11$. Или Вы какую-то необычную запись подстановок используете?

-- Чт авг 06, 2009 23:40:17 --

А, кажись понял! Вы подстановки не в виде произведения непересекающихся циклов расписываете, а как бы в два ряда, в первом --- числа от $1$ до $11$ в порядке возрастания, а во втором --- те числа, в которые подстановка переводит числа первого ряда. Ну и первый ряд не пишете.

Другими словами, в более традиционной записи $P_2 = (2,10)(3,9)(4,8)(5,7)$.

-- Чт авг 06, 2009 23:54:04 --

Также

$P_1 = (1,6,5,4,3,2) = (1,6)(1,5)(1,4)(1,3)(1,2)$
$P_3 = (1,9)(2,8)(3,7)$
$P_4 = (1,7)(2,11)(6,8)$
$P = (1,4,2,6,5)(7,10,8,9,11) = (1,4)(1,2)(1,6)(1,5)(7,10)(7,8)(7,9)(7,11)$

Легче не стало

-- Пт авг 07, 2009 00:04:48 --

Зато стало удобнее перемножать. Например

$P_1P_2 = (1,6,5,4,3,2)(2,10)(3,9)(4,8)(5,7) = (1,6,5,4,3,10,2)(3,9)(4,8)(5,7) = (1,6,5,4,9,3,10,2)(4,8)(5,7) = (1,6,5,8,4,9,3,10,2)(5,7) = (1,6,7,5,8,4,9,3,10,2)$

--- цикл длины $10$, выписывается сразу без всяких проблем

-- Пт авг 07, 2009 00:13:31 --

Похоже, тут подстановки так подобраны, что в каждую транспозицию, входящую в разложение $P_2, P_3, P_4$, входит ровно одно число, входящее в цикл, из которого составлена $P_1$. Наверняка это сделано специально

-- Пт авг 07, 2009 00:25:35 --

Во чё заметил: $(P_2P_1)^2 = (5,4,3,2,1)(6,7,8,9,10)$. Тоже наверняка не случайно

-- Пт авг 07, 2009 01:14:18 --

Затянула задача Больше часа уже мучаюсь с бумажкой, всё время кажется, что вот-вот, но, увы...

Большая просьба к автору: Вы когда нужную факторизацию найдёте, напишите её здесь, пожалуйста. Очень интересно посмотреть ответ!!!

[maxal]

arseniiv в сообщении #233331 писал(а):

Вот что известно:
$P = \left( {4,6,3,2,1,5,10,9,11,8,7} \right)$
$P_1 = \left( {6,1,2,3,4,5,7,8,9,10,11} \right)$
$P_2 = \left( {1,10,9,8,5,6,7,4,3,2,11} \right)$
$P_3 = \left( {9,8,7,4,5,6,3,2,1,10,11} \right)$
$P_4 = \left( {7,11,3,4,5,8,1,6,9,10,2} \right)$
Порядки порождаемых циклических групп (я это учитывал и не умножал $P_2$ на $P_2$ и пр.):
$P_1^6 = P_2^2 = P_3^2 = P_4^2 = e$

Вот решение в SAGE (который также использует GAP):

sage: P1=[6,1,2,3,4,5,7,8,9,10,11]
sage: P2=[1,10,9,8,5,6,7,4,3,2,11]
sage: P3=[9,8,7,4,5,6,3,2,1,10,11]
sage: P4=[7,11,3,4,5,8,1,6,9,10,2]
sage: G = PermutationGroup([P1,P2,P3,P4])
sage: G.gens()
[(2,10)(3,9)(4,8), (1,6,5,4,3,2), (1,7)(2,11)(6,8), (1,9)(2,8)(3,7)]
sage: P=G([4,6,3,2,1,5,10,9,11,8,7])     
sage: P.word_problem(G.gens(),False)
('x1*x2*x3*x2^-1*x4*x2^-1*x1^-1*x2*x1^-1*x2^-1*x1^-1*x2*x1^-1*x2^-1*x4*x2^-1*x4^-1*x2*x4^-1*x1^-1*x2*x1^-1*x2^-1*x3*x2^-1*x3*x2*x3*x2^-1*x4^-1*x2*x1^-1',
...

В этом результате x1=P2, x2=P1, x3=P4, x4=P3.

[Профессор Снэйп]

maxal в сообщении #233437 писал(а):

arseniiv в сообщении #233331 писал(а):

Вот что известно:
$P = \left( {4,6,3,2,1,5,10,9,11,8,7} \right)$
$P_1 = \left( {6,1,2,3,4,5,7,8,9,10,11} \right)$
$P_2 = \left( {1,10,9,8,5,6,7,4,3,2,11} \right)$
$P_3 = \left( {9,8,7,4,5,6,3,2,1,10,11} \right)$
$P_4 = \left( {7,11,3,4,5,8,1,6,9,10,2} \right)$
Порядки порождаемых циклических групп (я это учитывал и не умножал $P_2$ на $P_2$ и пр.):
$P_1^6 = P_2^2 = P_3^2 = P_4^2 = e$

Вот решение в SAGE (который также использует GAP):

sage: P1=[6,1,2,3,4,5,7,8,9,10,11]
sage: P2=[1,10,9,8,5,6,7,4,3,2,11]
sage: P3=[9,8,7,4,5,6,3,2,1,10,11]
sage: P4=[7,11,3,4,5,8,1,6,9,10,2]
sage: G = PermutationGroup([P1,P2,P3,P4])
sage: G.gens()
[(2,10)(3,9)(4,8), (1,6,5,4,3,2), (1,7)(2,11)(6,8), (1,9)(2,8)(3,7)]
sage: P=G([4,6,3,2,1,5,10,9,11,8,7])     
sage: P.word_problem(G.gens(),False)
('x1*x2*x3*x2^-1*x4*x2^-1*x1^-1*x2*x1^-1*x2^-1*x1^-1*x2*x1^-1*x2^-1*x4*x2^-1*x4^-1*x2*x4^-1*x1^-1*x2*x1^-1*x2^-1*x3*x2^-1*x3*x2*x3*x2^-1*x4^-1*x2*x1^-1',
...

В этом результате x1 надо трактовать как P1 и т.д.

Ой-ой-ой, я $P_2$ неправильно записал и столько времени уже мучаюсь!!! Все гипотезы строил на том, что $P_2$ состоит из четырёх транспозиций, а она из трёх, ничего себе!

Вообще ответ, конечно, краткостью не страдает Наверняка можно что-то подсократить. Хотя бы писать $P_2$ вместо $P_2^{-1}$, всё-таки $P_2^2 = e$

-- Пт авг 07, 2009 03:16:39 --

Н-да... А интересно, этот SAGE не мог более короткий ответ просмотреть?

-- Пт авг 07, 2009 03:18:28 --

maxal в сообщении #233437 писал(а):

В этом результате x1=P2, x2=P1, x3=P4, x4=P3.

Ой, тут ещё и индексы переставлены... Как всё плохо

-- Пт авг 07, 2009 03:25:42 --

Кстати, топикстартер зря писал

arseniiv в сообщении #233318 писал(а):

...перебором слишком долго...

Я то думал, перестановки длинные, из сотен элементов состоят. А тут всё дело происходит внутри $S_{11}$, так что компьютерный перебор никаких трудностей не представляет ($11! = 39916800$, для компутера это немного).

Может, SAGE тоже перебором всё делал?

[maxal]

Профессор Снэйп в сообщении #233439 писал(а):

Я то думал, перестановки длинные, из сотен элементов состоят. А тут всё дело происходит внутри $S_{11}$, так что компьютерный перебор никаких трудностей не представляет ($11! = 39916800$, для компутера это немного).

Может, SAGE тоже перебором всё делал?

Нет, SAGE (а точнее GAP, который он вызывает) решает не перебором, иначе результат не был бы таким длинным.
Для $S_{11}$ задачу нахождения минимального представления данной перестановки в виде произведения генераторов действительно можно решить динамическим программированием.
А вообще, найти минимальное представление гораздо сложнее чем просто некоторое. У GAP есть две различные функции для этих двух задач (см. по ссылке выше), и вычислительная сложность у них существенно различная. SAGE решает только вторую задачу (без требования минимальности).

[arseniiv]

Это подстановки из головоломки, диск, крутящийся в разных направлениях. Я "разобрал" и теперь не могу "собрать". Пришлось модель придумывать, вот как далеко зашло... Я тоже в GAP указанным способом попробовал, даже два раза. Непосредственной проверкой всё вычислено правильно, но передвижения диска руками ничего хорошего не дают... Видимо, что-то перепутал или в подстановках, или в своих обозначениях... Но результат есть, спасибо вам за помощь! Хотя бы теперь у меня есть GAP.

А насчёт "маленького" перебора в $S_{11}$ - может, я его не правильно делал, раз ничего не добился и пришлось перейти даже к вероятностному алгоритму, который тоже ничего не дал...

-- Пт авг 07, 2009 21:12:05 --

Ничего не понимаю, почему-то опять не получается. (Вчера два раза факторизовал, с идентичным результатом. Сегодня всю модель перепроверил и ещё раз то же самое.) Может, кто-нибудь знает вероятную причину. Я факторизую $P$, проверяю = действительно $P$. Тогда я выполняю действия в соответствии с полученным разложением и смотрю на диск. Известны его предыдущее состояние $a$ и текущее $b$. $aP = b \Leftrightarrow a^{ - 1} b = P$. Но у меня почему-то $a^{ - 1} b \ne P$! Т.к. в правильности разложения я не сомневаюсь, а все повороты записаны подстановками правильно, не знаю, что делать.

[vvvv]

Интересно, SAGE найдет решение для группы кубика Рубика?

[maxal]

vvvv в сообщении #233599 писал(а):

Интересно, SAGE найдет решение для группы кубика Рубика?

Да, конечно. Кроме того, для кубика Рубика у SAGE есть много специальных функций:
http://www.sagemath.org/doc/reference/s ... group.html

-- Fri Aug 07, 2009 12:14:14 --

Вот еще полезная статейка:
S.Egner, M.Puschel Solving Puzzles related to Permutation Groups

[Профессор Снэйп]

arseniiv в сообщении #233528 писал(а):

Т.к. в правильности разложения я не сомневаюсь, а все повороты записаны подстановками правильно, не знаю, что делать.

Да, тяжёлый случай

Я помню, когда ещё что-то программировал, можно было баг в программе часами или даже сутками искать. Всё на десять раз перепроверено, всё вроде Ок, а работает не так, как надо. Потом, когда баг всё же находится, думаешь: "Где были мои глаза?!"

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

Кстати, Вы перестановки перемножаете слева направо или справо налево? А GAP? Может, здесь причина несостыковки?

[arseniiv]

Слева направо. А GAP -тайна за семью печатями, в руководстве не описывается реализация. Так они же по определению транзитивны... Не должно же быть разницы

[Профессор Снэйп]

Транзитивность-то есть, но результат ведь всё равно разный. Коммутативности нет