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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
31.12.2013, 00:58     Как реализовать перемножение перестановок #1
Ребят, такой вопрос. Как реализовать перемножение перестановок? Кто нибудь может подсказать? Кинуть что-то подобное? Алгоритм подсказать? Помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
01.01.2014, 00:32     Как реализовать перемножение перестановок #21
Можно продолжать до S12 включительно )
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
01.01.2014, 11:44  [ТС]     Как реализовать перемножение перестановок #22
IrineK, расскажите мне, как это сделать?))) Очень интересно)
IrineK
Заблокирован
02.01.2014, 00:11     Как реализовать перемножение перестановок #23
Цитата Сообщение от 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. Все это хранится в соответствующей структуре.

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

Вот и всё )
Relike
 Аватар для Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
02.01.2014, 00:44  [ТС]     Как реализовать перемножение перестановок #24
IrineK, Аплодирую стоя! А можно с вами связаться по вопросам? В каком либо мессенжере, где будет удобней их задать? Skype, mail, vk... Буду признателен! Спасибо!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.01.2014, 20:29     Как реализовать перемножение перестановок
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
IrineK
Заблокирован
03.01.2014, 20:29     Как реализовать перемножение перестановок #25
Вот хэдер с реализацией алгоритма, описанного выше:

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;
}
Yandex
Объявления
03.01.2014, 20:29     Как реализовать перемножение перестановок
Ответ Создать тему
Опции темы

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