@Relike

Ребят, такой вопрос. Как реализовать перемножение перестановок? Кто нибудь может подсказать? Кинуть что-то подобное? Алгоритм подсказать? Помогите пожалуйста.

0

@Ev_Hyper

опишите задачу более детально

1

@Relike

Ev_Hyper, Я хочу попробовать реализовать нахождение матрицы Кели. Препод когда-то просил. И вот, мне нужно предварительно написать программу для перемножения двух перестановок...у меня уже зелёный дым из мозга валит....

0

Байт

Для начала надо увидеть. как вы представляете перестановку. В виде массива int-ов? Или еще как-то... Т.е. нужно увидеть. в каком направлении вы движитесь.

0

@Ev_Hyper

а в чем суть матрицы Кэли?

0

@Relike

Байт, лично мои соображения, что перестановку лучше записывать двумерным массивом 2xN. Какие данные? Мне нужно сделать так чтобы программа получала две перестановки, и перемножала их... На листке бумаги я это за пол минуты сделаю, а так туже...

Добавлено через 2 минуты
Ev_Hyper, Это долгая история. Зачем в теорию групп углубляться?) Даже в её самое введение) Перестановки, если я не ошибаюсь, это в курсе линейтной алгебры изучалось (не помню, помню только как решать). Если надо завтра будет теория, меня небыло на половине этой лекции и у меня только часть теории до завтрашнего дня. Сначало нужно разобраться с перестановкаи т.к. в основном работаем с ними

Добавлено через 1 минуту
Байт, Сначала не понял. Да, я думаю оптимально будет в виде массива...но вот как тут с циклами быть...я не знаю, надо скобку отловить (я про вот это (1,2,3)(4,5)(6,7) например)

0

Байт

Это в представлении int-массивов записывается так
2 3 1 5 4 7 6 (На i-том месте стоит то, куда переходит элемент i) И умножать такие перестановки - одно удовольствие)

0

@Ev_Hyper

общего развития ради

ох, линейка у меня на 3, и то не твердую была.

Если скинете на краткую теорию ссылку буду очень рад

0

Байт

- скорее, теория групп. Но алгебра - это да.

0

@Relike

Ev_Hyper, в учебнике нашего преподавателя по алгебре есть всё это. Он есть в интернете.

Добавлено через 29 секунд
Ev_Hyper, Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г

1

@Ev_Hyper

я не знаю вашего преподователя. Не знаю и теорию групп, так что вряд-ли первое что мне попадется будет толковым.

Добавлено через 13 секунд
спасибо

1

@Relike

Ev_Hyper, А.Г. Курош "Теория групп" и еще М.И. Карагаполов и Ю.И. Мерзляков "Основы теории групп".
У меня еще эти есть учебники, но нам вот Яцкин лекции по своему читает.

0

@Ev_Hyper

Но там нет упоминания о матрице Кэли, хотя и понятно написано что такое перестановки

а, в этой книге матрицу Кэли еще называют таблицей? Завтра почитаю

1

@Relike

Ev_Hyper, да, таблица. Я тоже понимаю что такое перестановки, я немогу додуматься как это запрограммировать всё дело))))

0

@IrineK

С помощью матриц представлений.

Пусть матрица перестановки G - это P(G), а перестановки T - P(T).
Тогда матрица произведения этих перестановок
P (GoT) = P(T) * P(G)

Потом пишем пару сотен строк незатейливого кода и в результате для группы S3 имеем:

Миниатюры

 

1

@IrineK

Прикольная головоломка под Новый год.
Теперь буду думать, как обобщить на SN.

1

@Relike

IrineK, отлично сделано! Подскажите как реализовать перемножение? На примере первых перестановок S4. Думаю пойму... Я не знаю как это безобразие запрограммировать.

Добавлено через 3 минуты
IrineK, только в S4 будет 24 перестановки...веселья уйма =)

0

Байт

Усе!

Добавлено через 35 минут
Конечно, тк. мы находимся в разделе С++, удобнее нумеровать элементы с нуля и так же записывать перестановки. Тогда выше приведенная перестановочка будет выглядеть так: 1 2 0 4 3 6 5, и -1 в последней скобочке не нужен.

Добавлено через 10 минут
Приведенный пример перестановки был слишком прост и частен. Поэтому, чтоб не вводить в заблуждение, возьмем другую. Пусть она в виде циклов записывается (0 2 4) ( 1 3) (5 6) Тогда в виде int - массива она будет записываться так: 2 3 4 1 0 6 5
Перевод из записи в виде циклов в целый массив - задача не сложная. Обратно - тоже.
С наступающим!

0

@IrineK

Чтобы понять, как соотносятся перестановки и их представления в виде матриц, смотрим ниже.
Правда, в угоду общности задачи, нумерация перестановок типа G теперь произвольная.
В целом расшифровка названий такая:
Е - единичная перестановка
G - перестановки, где есть неподвижные элементы
Р - все остальные перестановки

Миниатюры

 

1

@IrineK

Все возможные перестановки генерятся автоматически.
Вот и S4:

Миниатюры

   

1