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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программирование с использованием файлов http://www.cyberforum.ru/cpp-beginners/thread1060984.html
Помогите начинающему программисту: Распечатать анкетные данные студентов-отличников из интересующей вас группы HELPPPPPPPPPPPP!!!!!!!!!!!!!!
C++ Вывести список очередности предоставления мест в общежитии. Помогите написать КОД: Для получения места в общежитии формируется список студентов, который включает ФИО студента, группу, средний балл, доход на члена семьи. Общежитие в первую очередь... http://www.cyberforum.ru/cpp-beginners/thread1060983.html
Реализовать поиск данных по ключевым словам на компьютере и в интернете C++
Получится ли написать программу с интерфэйсом?Ну что-то пишешь,а она отвечает ну или по словам находит то что нужно или в компе или в инете...
Данные класса C++
Ребят, подскажите пожалуйста, как проинициализировать начальными значениями данные класса, допустим у меня есть класс: class Plane { public: XMMATRIX GetWorldMatrix(); Plane(); private:...
C++ Заданы матрицы А, В, С, D, каждая из которых содержит по три строчки и по три столбца. Перемножить матрицы Р и Q http://www.cyberforum.ru/cpp-beginners/thread1060963.html
Заданы матрицы А, В, С, D, каждая из которых содержит по три строчки и по три столбца. Перемножить матрицы Р и Q, полученные в результате сложения матриц: Р=А+В; Q=C+D. Сложение матриц оформить в...
C++ Эксперты! Одномерный массив неповторяющихся чисел не могу понять почему криво работает Задание: Нужно вывести массив из случайных чисел. Размер массива 8. Случайные числа от 1 до 8. Числа не должны повторяться. #include <iostream> #include <cstdlib> #include <ctime> using... подробнее

Показать сообщение отдельно
IrineK
Заблокирован
02.01.2014, 00:11
Цитата Сообщение от Relike Посмотреть сообщение
Очень интересно)
Вопрос перемножения матриц - самое легкое в этой задаче.

Задача в принципе в другом - научить комп генерить все возможные перестановки для группы SN данного порядка N.
Я свела данный процесс к итерации создания матриц представлений.

1) Начальный шаг N = 2.
Задаем матрицы представлений для двух возможных перестановок (1)(2) и (1,2)
или:
1 2
1 2
и
1 2
2 1
Матрицы представлений Р2(1) и Р2(2)
1 0
0 1
и
0 1
1 0

2) Первый шаг итерации N = 3
У нас шесть возможных перестановок
(1)(2)(3), (1,2,3), (1,3,2), (1)(2,3), (1,3)(2), (1,2)(3)
Если написать соответствующие матрицы представлений и "вглядеться", то видно следующую закономерность, которую легко реализовать программно.
Матрица Р2(1)
1 0
0 1
порождает при циклических постановках столбцов такие матрицы Р3(1), Р3(2), Р3(3)
1 0 0
0 1 0
0 0 1

0 1 0
0 0 1
1 0 0

0 0 1
1 0 0
0 1 0

Аналогично - матрица Р2(2) даст нам еще три матрицы Р3.

Что мы делаем:
в первой строке Р3 - выставляем 1 по очереди в каждом столбце i
размещаем первый столбец из Р2 в столбец (i+1) % 3
размещаем второй столбец из Р2 в столбец (i+2) % 3
Остаток от деления на 3 дает возможность изящно закодить циклическую перестановку.

3) Остается обобщить итерацию на любой последующий шаг.

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

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

Вот и всё )
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru