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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Relike
6 / 6 / 0
Регистрация: 24.04.2013
Сообщений: 260
#1

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

31.12.2013, 00:58. Просмотров 1528. Ответов 24
Метки нет (Все метки)

Ребят, такой вопрос. Как реализовать перемножение перестановок? Кто нибудь может подсказать? Кинуть что-то подобное? Алгоритм подсказать? Помогите пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.12.2013, 00:58     Как реализовать перемножение перестановок
Посмотрите здесь:

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

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

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

Как определить количество перестановок и сравнений - C++
У меня есть алгоритм Quicksort как определить количество перестановок и сравнений?? #include <iostream> #include <conio.h> #include...

Как найти в этой сортировке количество перестановок и сравнений? - C++
Как найти в этой сортировке количество перестановок и сравнений? void InsertSort(int *mas, int N) //сортировка вставками { int...

Как определить количество перестановок и сравнений в выборочной сортировке - C++
void choicesSort(int* Array, int length_array) { for (int repeat_counter(0); repeat_counter < length_array; repeat_counter++) ...

Как найти в данной сортировке количество перестановок и сравнений? - C++
void quicksort(int *mas, int first, int last) { int mid, count, m=0; int f=first, l=last; int count_compare=0, count_swap=0; ...

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

Добавлено через 3 минуты
IrineK, только в S4 будет 24 перестановки...веселья уйма =)
Байт
Эксперт C
15833 / 10160 / 1522
Регистрация: 24.12.2010
Сообщений: 19,151
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 - перестановки, где есть неподвижные элементы
Р - все остальные перестановки
Миниатюры
Как реализовать перемножение перестановок  
IrineK
Заблокирован
01.01.2014, 00:31     Как реализовать перемножение перестановок #20
Все возможные перестановки генерятся автоматически.
Вот и S4:
Миниатюры
Как реализовать перемножение перестановок   Как реализовать перемножение перестановок  
IrineK
Заблокирован
01.01.2014, 00:32     Как реализовать перемножение перестановок #21
Можно продолжать до S12 включительно )
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
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++
имею такой код #include &lt;iostream&gt; using namespace std; void qSort (int a,int nStart, int nEnd) { int L,R,c,X; if...

Где правильно ставить счетчики сравнений и перестановок, и как считать сложность этих алгоритмов? - C++
написал код двух сортировок, но не уверен, что правильно проставлены счетчики.#include &lt;iostream&gt; #include &lt;ctime&gt; #include &lt;conio.h&gt; ...

Перемножение матриц. - C++
Нужен код для перемножения матрицы и столбца за минимально возможное время. Порядок матрицы ( и столбца ) огромен - около 100000....

Перемножение матрицы - C++
матрица 1: int Matrica1() { int mas1; int i,j; cout &lt;&lt; &quot;The First Matrix&quot; &lt;&lt; endl; for(i=0;i&lt;10;i++) { ...


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

Или воспользуйтесь поиском по форуму:
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     Как реализовать перемножение перестановок
Ответ Создать тему
Опции темы

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