2014 dxdy logo

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

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




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

 
 
 
 Re: Алгоритм файторизации подстановки
Сообщение06.08.2009, 14:16 
Аватара пользователя
Если $P_1, \ldots, P_n$ --- все транспозиции, то, конечно, есть. А для произвольных $P_1, \ldots, P_n$ --- не знаю.

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

 
 
 
 Re: Алгоритм файторизации подстановки
Сообщение06.08.2009, 14:36 
Нет, увы, все они не транспозиции. А если представить их как произведения транспозиций, что-нибудь может получиться? А то из-за того, что группа $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 множителей

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

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

 
 
 
 Re: Алгоритм факторизации подстановки
Сообщение06.08.2009, 18:55 
Спасибо, maxal! :) Сейчас установлю и разложу себе на здоровье.

 
 
 
 Re: Алгоритм файторизации подстановки
Сообщение06.08.2009, 20:37 
Аватара пользователя
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 --

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

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

 
 
 
 Re: Алгоритм файторизации подстановки
Сообщение06.08.2009, 23:41 
Аватара пользователя
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.

 
 
 
 Re: Алгоритм файторизации подстановки
Сообщение07.08.2009, 00:04 
Аватара пользователя
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$ неправильно записал и столько времени уже мучаюсь!!! :oops: :twisted: :roll: Все гипотезы строил на том, что $P_2$ состоит из четырёх транспозиций, а она из трёх, ничего себе! :shock:

Вообще ответ, конечно, краткостью не страдает :) Наверняка можно что-то подсократить. Хотя бы писать $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.


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

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

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

arseniiv в сообщении #233318 писал(а):
...перебором слишком долго...


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

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

 
 
 
 Re: Алгоритм факторизации подстановки
Сообщение07.08.2009, 05:00 
Аватара пользователя
Профессор Снэйп в сообщении #233439 писал(а):
Я то думал, перестановки длинные, из сотен элементов состоят. А тут всё дело происходит внутри $S_{11}$, так что компьютерный перебор никаких трудностей не представляет ($11! = 39916800$, для компутера это немного).

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

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

 
 
 
 Re: Алгоритм факторизации подстановки
Сообщение07.08.2009, 13:54 
Это подстановки из головоломки, диск, крутящийся в разных направлениях. Я "разобрал" и теперь не могу "собрать". Пришлось модель придумывать, вот как далеко зашло... :wink: Я тоже в 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$! Т.к. в правильности разложения я не сомневаюсь, а все повороты записаны подстановками правильно, не знаю, что делать. :(

 
 
 
 Re: Алгоритм факторизации подстановки
Сообщение07.08.2009, 19:56 
Интересно, SAGE найдет решение для группы кубика Рубика?

 
 
 
 Re: Алгоритм факторизации подстановки
Сообщение07.08.2009, 20:12 
Аватара пользователя
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

 
 
 
 Re: Алгоритм факторизации подстановки
Сообщение07.08.2009, 20:15 
Аватара пользователя
arseniiv в сообщении #233528 писал(а):
Т.к. в правильности разложения я не сомневаюсь, а все повороты записаны подстановками правильно, не знаю, что делать.


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

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

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

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

 
 
 
 Re: Алгоритм факторизации подстановки
Сообщение07.08.2009, 20:48 
Слева направо. А GAP -тайна за семью печатями, в руководстве не описывается реализация. Так они же по определению транзитивны... :? Не должно же быть разницы

 
 
 
 Re: Алгоритм факторизации подстановки
Сообщение08.08.2009, 03:41 
Аватара пользователя
Транзитивность-то есть, но результат ведь всё равно разный. Коммутативности нет :)

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


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