Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.81/26: Рейтинг темы: голосов - 26, средняя оценка - 4.81
 Аватар для Relike
6 / 6 / 2
Регистрация: 24.04.2013
Сообщений: 260

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

31.12.2013, 00:58. Показов 5706. Ответов 25
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Ребят, такой вопрос. Как реализовать перемножение перестановок? Кто нибудь может подсказать? Кинуть что-то подобное? Алгоритм подсказать? Помогите пожалуйста.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
31.12.2013, 00:58
Ответы с готовыми решениями:

Как реализовать перемножение матриц?
#include <iostream> using namespace std; void main() { setlocale (LC_ALL, "RUS"); int Na,Ma,a; int i,j;

Реализовать алгоритм сортировка методом парных перестановок
1. Реализовать алгоритм сортировка методом парных перестановок. 2. Задана матрица размером N×M, N,M<50. Получить массив B,...

Реализовать алгоритм сортировка методом парных перестановок. Visual Studio2017
Реализовать алгоритм сортировка методом парных перестановок. VS2017

25
 Аватар для IrineK
2023 / 1641 / 425
Регистрация: 23.02.2011
Сообщений: 6,002
Записей в блоге: 25
01.01.2014, 00:32
Студворк — интернет-сервис помощи студентам
Можно продолжать до S12 включительно )
1
 Аватар для Relike
6 / 6 / 2
Регистрация: 24.04.2013
Сообщений: 260
01.01.2014, 11:44  [ТС]
IrineK, расскажите мне, как это сделать?))) Очень интересно)
0
 Аватар для IrineK
2023 / 1641 / 425
Регистрация: 23.02.2011
Сообщений: 6,002
Записей в блоге: 25
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
 Аватар для Relike
6 / 6 / 2
Регистрация: 24.04.2013
Сообщений: 260
02.01.2014, 00:44  [ТС]
IrineK, Аплодирую стоя! А можно с вами связаться по вопросам? В каком либо мессенжере, где будет удобней их задать? Skype, mail, vk... Буду признателен! Спасибо!
0
 Аватар для IrineK
2023 / 1641 / 425
Регистрация: 23.02.2011
Сообщений: 6,002
Записей в блоге: 25
03.01.2014, 20:29
Вот хэдер с реализацией алгоритма, описанного выше:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//генератор матриц представления для групп перестановок порядка 2 <= N <= 12 
 
#include <stdio.h>
#include <stdlib.h>
 
//вся группа в матричном представлении
typedef struct _MGroup
{   int dim;    //размерность группы
    int all;    //общее кво элементов (перестановок)
    int ***m;   //указатель на массив матриц всех элементов (перестановок) all x dim x dim
} MGroup;
 
//создаем квадратную матрицу NxN
int **CreateMatrixNxN (int N)
{   int i,j;
    int **res = (int**) malloc (N*sizeof(int*));
    for (j = 0; j<N; j++)                       //строим не по строкам, а по столбцам, почему - понятно из алгоритма
        res[j] = (int*) malloc (N*sizeof(int));
 
    for (j = 0; j<N; j++)       //сразу заполняем нулями
        for (i = 0; i<N; i++)
            res[i][j] = 0;
 
    return res;
}
 
//освобождаем память от матрицы NxN
void DestroyMatrixNxN (int **M, int N)
{   int j = N;
    while (--j > -1)
        free (M[j]);
    free (M);
}
 
//просто факториал )
int fact (int N)
{   if (!N)
        return 1;
    
    int res = N;
    while (--N)
        res *= N;
    return res;
}
 
//создаем группу как совокупность всех матриц перестановок - N! штук размерностью NxN
MGroup *CreateGroup (int DIM)
{   MGroup *group = (MGroup*) malloc (sizeof(MGroup));
    group->dim = DIM;
    group->all = fact (DIM);
 
    group->m = (int***) malloc (group->all * sizeof(int**));
    for (int k = 0; k<group->all; k++)
        group->m[k] = CreateMatrixNxN (DIM);
    
    return group;
}
 
//освобождаем память от группы
void DestroyGroup (MGroup *group)
{   int k = group->all;
    while (--k > -1)
        DestroyMatrixNxN (group->m[k], group->dim);
    free (group->m);
    free (group);
}
 
//вывод на экран отдельной матрицы перестановки
void ShowMatrixNxN (int **M, int N)
{   int i,j;
    for (j = 0; j<N; j++)
    {   for (i = 0; i<N; i++)
            printf("%5d", M[i][j]);
        printf("\n");
    }
    printf("\n");
}
 
//вывод на экран всей группы - всех матриц перестановок
void ShowGroup (MGroup *group)
{   int all = group->all;
    for (int k = 0; k<all; k++)
        ShowMatrixNxN (group->m[k], group->dim);
}
 
//начало итерации - заполнение двух матриц группы S2
MGroup *CreateS2 ()
{   MGroup *S2 = CreateGroup (2);
    S2->m[0][0][0] = S2->m[0][1][1] = 1;
    S2->m[1][0][1] = S2->m[1][1][0] = 1;
    return S2;
}
 
//подстановка столбцов матрицы предыдущей итерации в матрицу 
//итерации текущей
void FillColumnPrev (int *cur, int *prev, int N)
{   for (int i = 1; i<N; i++)
        cur[i] = prev[i-1];
}
 
//чисто символически )
void FillColumnOne (int *col)
{   col[0] = 1;
}
 
//собственно - решение задачи
MGroup *CreateSN (int N)
{   int indPrev = 2, indNext = 3, i, j, k, qPrev = 1, qNext;
    MGroup *prev = CreateS2 ();
    MGroup *next;
 
    while (indPrev < N)
    {   next = CreateGroup (indNext);
        for (i = 0, qNext = 0, qPrev *= indPrev; i<qPrev; i++)
        {   for (j = 0; j<indNext; j++, qNext++)
            {   FillColumnOne (next->m[qNext][j]);
                for (k = 1; k<indNext; k++)
                    FillColumnPrev (next->m[qNext][(j+k)%indNext], prev->m[i][k-1], indNext);
            }
        }
        indPrev++;
        indNext++;
        DestroyGroup (prev);
        prev = next;
    }
    return prev;
}
1
0 / 0 / 3
Регистрация: 09.10.2013
Сообщений: 189
09.03.2020, 13:09
Матрица Кэли- это таблица умножения группы. Что бы представить, то по сути таблицей Кэли явяется судоку без ограничения на квадраты. То есть в каждой строке и каждом столбце все элементы различны и они являются перестановкой
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
09.03.2020, 13:09

Реализовать перемножение двух матриц 2х2 на основании данных варианта задания
2. Реализовать перемножение двух матриц 2х2 на основании данных варианта задания(1 2 3 4 5 6 7 8 ). Результат в виде таблицы значений...

Как определить количество перестановок и сравнений
У меня есть алгоритм Quicksort как определить количество перестановок и сравнений?? #include &lt;iostream&gt; #include &lt;conio.h&gt; ...

Реализовать алгоритм перестановок.
Вход: M-множество, элементы которого можно поставить на i-e место; i-заполняемое место в последовательности P. Выход:...

Реализовать перемножение двух матриц
Реализовать перемножение двух матриц 2х2 ( первая матрица - первая строка 1 2 ,вторая строка 3 1) (вторая матрица -первая строка 1 1 ,...

Реализовать перемножение двух матриц 2х2
Задания: 1. Заполнить статический массив значениями (88, 112, 6467, 325, 878, 3, 77, 8, 99). Результат в виде таблицы значений массива...


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

Или воспользуйтесь поиском по форуму:
26
Ответ Создать тему
Новые блоги и статьи
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
Транслитерация текста с кириллицы на латиницу (вариант №1)
Maks 11.11.2026
Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru