Форум программистов, компьютерный форум CyberForum.ru

Как реализовать перемножение перестановок - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
31.12.2013, 00:58     Как реализовать перемножение перестановок #1
Ребят, такой вопрос. Как реализовать перемножение перестановок? Кто нибудь может подсказать? Кинуть что-то подобное? Алгоритм подсказать? Помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ev_Hyper
 Аватар для Ev_Hyper
1806 / 1627 / 435
Регистрация: 15.12.2013
Сообщений: 5,784
31.12.2013, 01:08     Как реализовать перемножение перестановок #2
опишите задачу более детально
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
31.12.2013, 01:33  [ТС]     Как реализовать перемножение перестановок #3
Ev_Hyper, Я хочу попробовать реализовать нахождение матрицы Кели. Препод когда-то просил. И вот, мне нужно предварительно написать программу для перемножения двух перестановок...у меня уже зелёный дым из мозга валит....
Байт
 Аватар для Байт
13969 / 8800 / 1226
Регистрация: 24.12.2010
Сообщений: 15,944
31.12.2013, 01:41     Как реализовать перемножение перестановок #4
Цитата Сообщение от Relike Посмотреть сообщение
Как реализовать перемножение перестановок?
Для начала надо увидеть. как вы представляете перестановку. В виде массива int-ов? Или еще как-то... Т.е. нужно увидеть. в каком направлении вы движитесь.
Покажи мне свои данные, а уж как их обработать, я попробую догадаться.
Ev_Hyper
 Аватар для Ev_Hyper
1806 / 1627 / 435
Регистрация: 15.12.2013
Сообщений: 5,784
31.12.2013, 01:43     Как реализовать перемножение перестановок #5
а в чем суть матрицы Кэли?
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
31.12.2013, 01:48  [ТС]     Как реализовать перемножение перестановок #6
Байт, лично мои соображения, что перестановку лучше записывать двумерным массивом 2xN. Какие данные? Мне нужно сделать так чтобы программа получала две перестановки, и перемножала их... На листке бумаги я это за пол минуты сделаю, а так туже...

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

Добавлено через 1 минуту
Байт, Сначала не понял. Да, я думаю оптимально будет в виде массива...но вот как тут с циклами быть...я не знаю, надо скобку отловить (я про вот это (1,2,3)(4,5)(6,7) например)
Байт
 Аватар для Байт
13969 / 8800 / 1226
Регистрация: 24.12.2010
Сообщений: 15,944
31.12.2013, 01:54     Как реализовать перемножение перестановок #7
Цитата Сообщение от Relike Посмотреть сообщение
это (1,2,3)(4,5)(6,7) например)
Это в представлении int-массивов записывается так
2 3 1 5 4 7 6 (На i-том месте стоит то, куда переходит элемент i) И умножать такие перестановки - одно удовольствие)
Ev_Hyper
 Аватар для Ev_Hyper
1806 / 1627 / 435
Регистрация: 15.12.2013
Сообщений: 5,784
31.12.2013, 01:55     Как реализовать перемножение перестановок #8
Цитата Сообщение от Relike Посмотреть сообщение
Это долгая история. Зачем в теорию групп углубляться?) Даже в её самое введение)
общего развития ради

Цитата Сообщение от Relike Посмотреть сообщение
Перестановки, если я не ошибаюсь, это в курсе линейтной алгебры изучалось (не помню, помню только как решать)
ох, линейка у меня на 3, и то не твердую была.

Если скинете на краткую теорию ссылку буду очень рад
Байт
 Аватар для Байт
13969 / 8800 / 1226
Регистрация: 24.12.2010
Сообщений: 15,944
31.12.2013, 01:58     Как реализовать перемножение перестановок #9
Цитата Сообщение от Relike Посмотреть сообщение
в курсе линейной алгебры изучалось
- скорее, теория групп. Но алгебра - это да.
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
31.12.2013, 02:01  [ТС]     Как реализовать перемножение перестановок #10
Ev_Hyper, в учебнике нашего преподавателя по алгебре есть всё это. Он есть в интернете.

Добавлено через 29 секунд
Ev_Hyper, Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г
Ev_Hyper
 Аватар для Ev_Hyper
1806 / 1627 / 435
Регистрация: 15.12.2013
Сообщений: 5,784
31.12.2013, 02:02     Как реализовать перемножение перестановок #11
я не знаю вашего преподователя. Не знаю и теорию групп, так что вряд-ли первое что мне попадется будет толковым.

Добавлено через 13 секунд
Цитата Сообщение от Relike Посмотреть сообщение
Ev_Hyper, Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г
спасибо
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
31.12.2013, 02:04  [ТС]     Как реализовать перемножение перестановок #12
Ev_Hyper, А.Г. Курош "Теория групп" и еще М.И. Карагаполов и Ю.И. Мерзляков "Основы теории групп".
У меня еще эти есть учебники, но нам вот Яцкин лекции по своему читает.
Ev_Hyper
 Аватар для Ev_Hyper
1806 / 1627 / 435
Регистрация: 15.12.2013
Сообщений: 5,784
31.12.2013, 02:11     Как реализовать перемножение перестановок #13
Цитата Сообщение от Relike Посмотреть сообщение
У меня еще эти есть учебники, но нам вот Яцкин лекции по своему читает.
Но там нет упоминания о матрице Кэли, хотя и понятно написано что такое перестановки

Цитата Сообщение от Relike Посмотреть сообщение
А.Г. Курош "Теория групп"
а, в этой книге матрицу Кэли еще называют таблицей? Завтра почитаю
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
31.12.2013, 02:12  [ТС]     Как реализовать перемножение перестановок #14
Ev_Hyper, да, таблица. Я тоже понимаю что такое перестановки, я немогу додуматься как это запрограммировать всё дело))))
IrineK
Заблокирован
31.12.2013, 14:55     Как реализовать перемножение перестановок #15
Цитата Сообщение от Relike Посмотреть сообщение
как это запрограммировать всё дело
С помощью матриц представлений.

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

Потом пишем пару сотен строк незатейливого кода и в результате для группы S3 имеем:
Миниатюры
Как реализовать перемножение перестановок  
IrineK
Заблокирован
31.12.2013, 14:58     Как реализовать перемножение перестановок #16
Прикольная головоломка под Новый год.
Теперь буду думать, как обобщить на SN.
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
31.12.2013, 18:12  [ТС]     Как реализовать перемножение перестановок #17
IrineK, отлично сделано! Подскажите как реализовать перемножение? На примере первых перестановок S4. Думаю пойму... Я не знаю как это безобразие запрограммировать.

Добавлено через 3 минуты
IrineK, только в S4 будет 24 перестановки...веселья уйма =)
Байт
 Аватар для Байт
13969 / 8800 / 1226
Регистрация: 24.12.2010
Сообщений: 15,944
31.12.2013, 19:14     Как реализовать перемножение перестановок #18
Цитата Сообщение от Байт Посмотреть сообщение
Это в представлении int-массивов записывается так
2 3 1 5 4 7 6 (На i-том месте стоит то, куда переходит элемент i) И умножать такие перестановки - одно удовольствие)
C++
1
2
3
 int A[N], B[N]; // перемножаемые перестановки.
 int C[N];  // Их произведение A*B
 for(i=0; i<N;i++) C[i] = B[A[i]-1];
Усе!

Добавлено через 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
Перевод из записи в виде циклов в целый массив - задача не сложная. Обратно - тоже.
С наступающим!
IrineK
Заблокирован
01.01.2014, 00:21     Как реализовать перемножение перестановок #19
Чтобы понять, как соотносятся перестановки и их представления в виде матриц, смотрим ниже.
Правда, в угоду общности задачи, нумерация перестановок типа G теперь произвольная.
В целом расшифровка названий такая:
Е - единичная перестановка
G - перестановки, где есть неподвижные элементы
Р - все остальные перестановки
Миниатюры
Как реализовать перемножение перестановок  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.01.2014, 00:31     Как реализовать перемножение перестановок
Еще ссылки по теме:

Как подсчитать произведенное количество перестановок при быстрой сортировке? C++
Как найти в этой сортировке количество перестановок и сравнений? C++
Как найти в данной сортировке количество перестановок и сравнений? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
IrineK
Заблокирован
01.01.2014, 00:31     Как реализовать перемножение перестановок #20
Все возможные перестановки генерятся автоматически.
Вот и S4:
Миниатюры
Как реализовать перемножение перестановок   Как реализовать перемножение перестановок  
Yandex
Объявления
01.01.2014, 00:31     Как реализовать перемножение перестановок
Ответ Создать тему
Опции темы

Текущее время: 15:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru