Выполнить операцию транспонирования прямоугольной матрицы A

@Romadxd · Регистрация: 16.11.2016

Author24 — интернет-сервис помощи студентам

Выполнить операцию транспонирования прямоугольной матрицы A(m,n),m<>n , не выделяя дополнительного массива для хранения результата. Матрицу представить в виде одномерного массива.

Байт · 16.08.2017, 11:17

Romadxd, Есть ли какие-нибудь собственные попытки, наброски? Хотя бы скелет программы?

@JohnyWalker · 16.08.2017, 12:59

Romadxd!
Не понятно, а можно ли вообще эту задачу решить в общем случае. Ведь матрицы могут быть не квадратными, что значит, что разные измерения у них имеют разную длину. Т. е. возможна матрица $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{m n}$ , у которой $https://www.cyberforum.ru/cgi-bin/latex.cgi?m \neq n$ . Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?A^T$ является матрицей, у которой, n строк и m столбцов, т. е. $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{n m}$ .

Если мы захотим представить двумерные матрицы двумерными массивами (самый естественный способ), то двумерный массив с размерностью $https://www.cyberforum.ru/cgi-bin/latex.cgi?m \times n$ никак не будет работать как массив с размерностью $https://www.cyberforum.ru/cgi-bin/latex.cgi?n \times m$ , устройство сишного массива (да и не только сишного) этого не позволяет. А после транспонирования именно это и должно произойти с этим массивом, ведь мы же хотим, чтобы результат транспонирования матрицы оказывался в том же массиве, что и исходная матрица.

Можно, конечно, взять указатель и выделить для него память в куче под $https://www.cyberforum.ru/cgi-bin/latex.cgi?m \times n$ ячеек. Доступ к этим ячейкам будет как в одномерном массиве, но зато этот участок памяти можно трактовать и как массив с размерностью $https://www.cyberforum.ru/cgi-bin/latex.cgi?m \times n$ , и как массив с размерностью $https://www.cyberforum.ru/cgi-bin/latex.cgi?n \times m$ , и в нём выполнить соответствующие перестановки элементов.

Я подумал сейчас, можно, наверное, и с двумерным массивом попробовать провернуть этот трюк через приведение типов массивов или указателей. Но с этим будет потом всё равно так неудобно работать, потому что массив останется с прежней исходной размерностью: $https://www.cyberforum.ru/cgi-bin/latex.cgi?m \times n$ не заменится у массива волшебным образом на $https://www.cyberforum.ru/cgi-bin/latex.cgi?n \times m$ .

Можно ещё использовать объединение — тип union, и объявить в нём два массива — один с одной размерностью, другой с обратной.

C

1
2
3

union
{double A[3][5];
 double B[5][3]; } Mx;

Самый простой путь решения, но смысла в нём тоже мало.

Так что определись, что у тебя за задача и что тебе на самом деле нужно. Если это задание в учебном заведении, надо уточнить, что имел в виду преподаватель.

Добавлено через 23 минуты

Сообщение от JohnyWalker

Я подумал сейчас, можно, наверное, и с двумерным массивом попробовать провернуть этот трюк через приведение типов массивов или указателей.

Попробовал сейчас это сделать, написав следующую программу.

C

int main()
{
 int A[3][5];
 ((int[5][3])A)[4][2] = 6;
 return 0; }

Скомпилировать это не получилось. Компилятор выдал ошибку

тип массива в операции приведения типа

Значит, стандарт языка такого не позволяет.

Остаётся изворачиваться только через указатели.

А вообще в задаче немного смысла. Задача (транспонировать матрицу, записывая результат в неё же саму) имеет смысл для квадратной матрицы, у которой обе размерности равны. Там она действительно просто решается.

@mid150 · 16.08.2017, 18:13

Если я всё правильно понял, то вот так:

C

#include<stdio.h>
#include<stdlib.h>
 
int main(void){
  
  //system("chcp 1251>nul"); //раскомментируйте, если не отображается кириллица
  
  int m,n;
  printf("Введите размеры матрицы:");
  scanf("%d %d",&m, &n);
 
  int **A= (int**) malloc(m*sizeof(int*));
  for(int i=0;i<m;i++)
     A[i]=(int*) malloc(n*sizeof(int*));
 
  printf("Заполните матрицу:\n");
  for(int i=0;i<m;i++)
     for(int j=0;j<n;j++){
        printf("A[%d][%d]=",i,j);
        scanf("%d",&A[i][j]);
     }
 
  printf("Полученная матрица:\n");
  for(int i=0;i<m;i++){
     for(int j=0;j<n;j++){
        printf("%d ",A[i][j]);
     }
     printf("\n");
  }
 
  printf("Результат транспонирования:");
  for(int i=0;i<n;i++)
     for(int j=0;j<m;j++)
        printf("%d ",A[j][i]);
  printf("\n");
  
  for(int i=0;i<m;i++)
      free(A[i]);
  free(A);
 
  return 0;
}

Байт · 16.08.2017, 22:09

JohnyWalker, mid150, А вы это видели?

Сообщение от Romadxd

Матрицу представить в виде одномерного массива.

И задача - пустяк. Небольшая игра с индексами, которая лично мне не прибавит ума. А вам может быть и интересна, и забавна.

Добавлено через 2 минуты
А вот заголовок темы

Линейная алгебра

и впрямь наводит на грустные мысли...

@mid150 · 17.08.2017, 06:47

Байт, мне думается, что нужно представлять в виде одномерного массива уже транспонированную матрицу, то есть ту, что получаем на выходе, то есть просто строка из символов входящих в матрицу. Если очень нужно, можно объявить таковой массив,заполнить его, а только потом выводить. Однако, так как одномерный массив в программе более негде не фигурирует, кроме как на выводе, то особого смысла в его объявлении я не вижу.

@JohnyWalker · 17.08.2017, 09:23

Сообщение от Байт

JohnyWalker, mid150, А вы это видели?

Сообщение от Romadxd

Матрицу представить в виде одномерного массива.

Нет, этого я не заметил. Иначе не написал бы свой пост №3.

Действительно можно взять одномерный массив размерностью M*N и рассматривать его и как двумерный [M][N], и как двумерный [N][M].

И задача - пустяк. Небольшая игра с индексами, которая лично мне не прибавит ума. А вам может быть и интересна, и забавна.

Тут ведь, как я понимаю, нужно взять этот массив с исходной матрицей и в него же записать транспонированную матрицу. То есть один и тот же буфер используется и для хранения исходной матрицы, и для записи в него результата транспонирования. Промежуточного буфера использовать нельзя. Начнёшь просто перезаписывать строки как столбцы — затрёшь часть чисел исходной матрицы и получишь неправильный результат. Мне вот в голову не приходит простого решения, как это можно сделать. И числа переставить в массиве, и исходные числа не затереть в процессе перестановки.

Добавлено через 58 минут
В общем, Байт, условие задачи понятно (оно вполне корректно после твоего уточнения), а как решить её, я не знаю. Сходу простого решения в голову не приходит.

Байт · 17.08.2017, 09:50

JohnyWalker, Элемент [i][j] в линейном представлении будет иметь индекс M*j + i
Транспонирование, это обмен [i][j] - [j][i]

C

for(j=0; j<N; j++)
  for(i=0; i<M; i++) {
     int t = A[M*j+i];
     A[M*j+i] = A[N*i+j];
     A[N*i+j] = t;
  }

Как-то так.
Проверьте, пожалуйста. (Если не лень)

@JohnyWalker · 17.08.2017, 13:42

Байт, проверил я твой пример очень тщательно. Не работает он. Твой вариант, это самое первое, что приходит в голову, и оно в общем-то работает для квадратных матриц. Но для прямоугольных матриц с разными размерами сторон оно работать не будет. Вот я сделал несколько тестов.

1. Твой алгоритм для прямоугольной матрицы размерностью 3*5.

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

C

#include <stdio.h>
 
 
#define M 3
#define N 5
 
 
int S[M][N] = 
{{ 1,  2,  3,  4,  5},
 { 6,  7,  8,  9, 10},
 {11, 12, 13, 14, 15}};
 
 
int main()
{ 
 int *A;
 int i, j;
 
 A = (int *)S;
 
 
 /* Выводим исходную матрицу. */
 
 printf("Исходная матрица:\n\n");
 
 for(i=0; i<M; i++) {
   for(j=0; j<N; j++)
      printf("%4d", A[N*i+j]);
   puts("");
 }
 
 printf("\n\n");
 
 
 /* Выполняем преобразование над матрицей. */
 
 for(j=0; j<N; j++)
   for(i=0; i<M; i++) {
      int t = A[M*j+i];
      A[M*j+i] = A[N*i+j];
      A[N*i+j] = t;
   }
 
 
 /* Выводим преобразованную матрицу. */
 
 printf("Преобразованная матрица:\n\n");
 
 for(i=0; i<N; i++) {
   for(j=0; j<M; j++)
      printf("%4d", A[M*i+j]);
   puts("");
 }
 
 printf("\n");
 
 return 0;
}

Он работает неправильно. Числа оказались на самых разных местах.

2. Тот же алгоритм, но для квадратной матрицы.

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

C

#include <stdio.h>
 
 
#define M 4
#define N 4
 
 
int S[M][N] = 
{{ 1,  2,  3,  4},
 { 5,  6,  7,  8},
 { 9, 10, 11, 12},
 {13, 14, 15, 16}};
 
 
int main()
{ 
 int *A;
 int i, j;
 
 A = (int *)S;
 
 
 /* Выводим исходную матрицу. */
 
 printf("Исходная матрица:\n\n");
 
 for(i=0; i<M; i++) {
   for(j=0; j<N; j++)
      printf("%4d", A[N*i+j]);
   puts("");
 }
 
 printf("\n\n");
 
 
 /* Выполняем преобразование над матрицей. */
 
 for(j=0; j<N; j++)
   for(i=0; i<M; i++) {
      int t = A[M*j+i];
      A[M*j+i] = A[N*i+j];
      A[N*i+j] = t;
   }
 
 
 /* Выводим преобразованную матрицу. */
 
 printf("Преобразованная матрица:\n\n");
 
 for(i=0; i<N; i++) {
   for(j=0; j<M; j++)
      printf("%4d", A[M*i+j]);
   puts("");
 }
 
 printf("\n");
 
 return 0;
}

Мы в результате преобразования получили исходную матрицу. В этом нет ничего удивительного, поскольку перестановка элементов [i,j] <--> [j,i] для любой пары i != j при таком алгоритме выполняется дважды — один раз в виде [i,j] <--> [j,i], а второй раз в виде [j,i] <--> [i,j]. Это двойное транспонирование, т. е. $https://www.cyberforum.ru/cgi-bin/latex.cgi?(A^T)^T=A$ , т. е. тождественное преобразование.

3. Исправленный и работающий алгоритм для квадратных матриц будет выглядеть так

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

C

#include <stdio.h>
 
 
#define M 4
#define N 4
 
 
int S[M][N] = 
{{ 1,  2,  3,  4},
 { 5,  6,  7,  8},
 { 9, 10, 11, 12},
 {13, 14, 15, 16}};
 
 
int main()
{ 
 int *A;
 int i, j;
 
 A = (int *)S;
 
 
 /* Выводим исходную матрицу. */
 
 printf("Исходная матрица:\n\n");
 
 for(i=0; i<M; i++) {
   for(j=0; j<N; j++)
      printf("%4d", A[N*i+j]);
   puts("");
 }
 
 printf("\n\n");
 
 
 /* Выполняем преобразование над матрицей. */
 
 for(j=0; j<N; j++)
   for(i=0; i<j; i++) {
      int t = A[M*j+i];
      A[M*j+i] = A[N*i+j];
      A[N*i+j] = t;
   }
 
 
 /* Выводим преобразованную матрицу. */
 
 printf("Преобразованная матрица:\n\n");
 
 for(i=0; i<N; i++) {
   for(j=0; j<M; j++)
      printf("%4d", A[M*i+j]);
   puts("");
 }
 
 printf("\n");
 
 return 0;
}

В таком виде он работает правильно.

4. Пробуем этот исправленный алгоритм применить к прямоугольной не квадратной матрице, хотя в этом смысла особого нет.

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

C

#include <stdio.h>
 
 
#define M 3
#define N 5
 
 
int S[M][N] = 
{{ 1,  2,  3,  4,  5},
 { 6,  7,  8,  9, 10},
 {11, 12, 13, 14, 15}};
 
 
int main()
{ 
 int *A;
 int i, j;
 
 A = (int *)S;
 
 
 /* Выводим исходную матрицу. */
 
 printf("Исходная матрица:\n\n");
 
 for(i=0; i<M; i++) {
   for(j=0; j<N; j++)
      printf("%4d", A[N*i+j]);
   puts("");
 }
 
 printf("\n\n");
 
 
 /* Выполняем преобразование над матрицей. */
 
 for(j=0; j<N; j++)
   for(i=0; i<j; i++) {
      int t = A[M*j+i];
      A[M*j+i] = A[N*i+j];
      A[N*i+j] = t;
   }
 
 
 /* Выводим преобразованную матрицу. */
 
 printf("Преобразованная матрица:\n\n");
 
 for(i=0; i<N; i++) {
   for(j=0; j<M; j++)
      printf("%4d", A[M*i+j]);
   puts("");
 }
 
 printf("\n");
 
 return 0;
}

Видим, что он не работает.

5. Пробуем тот же алгоритм 4., но в слегка изменённом виде

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

C

#include <stdio.h>
 
 
#define M 3
#define N 5
 
 
int S[M][N] = 
{{ 1,  2,  3,  4,  5},
 { 6,  7,  8,  9, 10},
 {11, 12, 13, 14, 15}};
 
 
int main()
{ 
 int *A;
 int i, j;
 
 A = (int *)S;
 
 
 /* Выводим исходную матрицу. */
 
 printf("Исходная матрица:\n\n");
 
 for(i=0; i<M; i++) {
   for(j=0; j<N; j++)
      printf("%4d", A[N*i+j]);
   puts("");
 }
 
 printf("\n\n");
 
 
 /* Выполняем преобразование над матрицей. */
 
 for(i=0; i<M; i++)
   for(j=0; j<i; j++) {
      int t = A[M*j+i];
      A[M*j+i] = A[N*i+j];
      A[N*i+j] = t;
   }
 
 
 /* Выводим преобразованную матрицу. */
 
 printf("Преобразованная матрица:\n\n");
 
 for(i=0; i<N; i++) {
   for(j=0; j<M; j++)
      printf("%4d", A[M*i+j]);
   puts("");
 }
 
 printf("\n");
 
 return 0;
}

Этот вариант тоже не работает, хотя где-то правильные куски в получившейся матрице и есть (но их очень мало).

Тут дело в том, что при записи в массив портятся входные данные (исходная матрица), а форматы обеих матриц очень разные (они имеют разную размерность - M*N и N*M), что не позволяет таким простым способом побороть этот эффект. Можешь все эти тесты странслировать у себя и убедиться, что это так, а заодно проверить, нет ли в них ошибок.

Эта задача не такая простая и она совсем не программистская, а скорее математическая. Это задача на перестановки элементов. Это маленькая головоломка. Может, она и имеет простое изящное решение, но я его не вижу.

Байт · 17.08.2017, 21:36

JohnyWalker, да, вы правы. Погорячился я. Не так все просто. И работа вами проделана большая.
По поводу двойного транспонирования - мой несомненный ляп.
Но вот тут

Сообщение от JohnyWalker

к прямоугольной не квадратной матрице, хотя в этом смысла особого нет.

имхо, вы не правы
Вот матрица (строка)
( 1, 2)
Вот она же транспонированная (столбец)
1
2
Самая обычная математическая операция. Часто используемая.
Сейчас нет особого настроения и времени, но обещаю заняться этим вопросом и свою ошибку исправить в ближайшее время

Добавлено через 17 минут
JohnyWalker, Посмотрел на примере 2 х 3
1 2 3
4 5 6
Линейная запись 1 2 3 4 5 6
Транспонированная
1 4
2 5
3 6
Линейная запись 1 4 2 5 3 6
Любопытная перестановка. Закон пока не улавливается. Думать надо.

@JohnyWalker · 17.08.2017, 21:39

Сообщение от Байт

Но вот тутимхо, вы не правы
Вот матрица (строка)
( 1, 2)
Вот она же транспонированная (столбец)
1
2

Там структура всего этого сложная и запутанная. Квадратная матрица симметричная (в смысле равенства своих сторон, а не в том смысле, что под этим понимают в линейной алгебре, конечно), и исходная, и результирующая транспонированная матрица естественно ложатся друг на друга. Поэтому простейший алгоритм и работает. А вот когда матрица прямоугольная, но не квадратная, и при этом обе матрицы с противоположным значением размеров должны находиться в одном буфере, не ложатся они так легко друг на друга. При их наложении возникает путаница и полное несоответствие одного другому. Поэтому и не проходит этот алгоритм в такой простой форме. Вы можете попробовать решить эту задачу, но это явно головоломка. Я с ней не стал разбираться, она не такая простая. На решение таких головоломок может уйти и месяц, и никакой гарантии, что до него додумаешься. И при этом практической пользы в задаче никакой. Может, она и очень просто решается, может, и нет. В общем, это головоломка на перестановки элементов. Сам этим не хочу заниматься. Вы можете попробовать чисто из спортивного интереса, не более.

Байт · 17.08.2017, 21:42

Не по теме:

Сообщение от JohnyWalker

тутимхо

Хорошее слово получилось, не правда ли?:)

@JohnyWalker · 17.08.2017, 21:43

Сообщение от Байт

1 2 3
4 5 6
Линейная запись 1 2 3 4 5 6
Транспонированная
1 4
2 5
3 6
Линейная запись 1 4 2 5 3 6
Любопытная перестановка. Закон пока не улавливается. Думать надо.

А впрочем, если задача вам нравится с чисто математической стороны, попробуйте из любви к искусству. Почему бы и нет

Ха... В приведённом вами примере закон как раз есть. Приглядитесь ближе

Только как его использовать...

Байт · 18.08.2017, 10:03

Немного подумав, пришел к таким выводам.
Пусть матрица A[N][M] представлена в линейной записи C[N*M].
Напечатать как матрицу А, так и матрицу транспонированную - тривиальная задача.
Столь же тривиальна задача - создать линейное представление D[M*N] транспонированной матрицы (в другой области памяти)
Задача существенно усложняется, если запрещается использование дополнительной памяти. И дело здесь не в вычислении линейного индекса на основе двойного, а в необходимости производить циклические перестановки довольно замысловатого вида.
Возможно, в решении этой задачи могла бы оказать помощь и Алгебра (Теория Групп, например)
Я все-таки не оставляю надежды, разобраться с этой задачей....

@УГнетатель · 19.08.2017, 09:20

2x2 http://ideone.com/ip7v3i

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

C

#include <stdio.h>
#include <stdlib.h>
 
void int_swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
 
void int_rotate(int* first, int* n_first, int* last)
{
    if (first == n_first) return;
    if (n_first == last) return;
 
    int* next = n_first;
    do {
        int_swap(first++, next++);
        if (first == n_first) n_first = next;
    } while (next != last);
 
    for (next = n_first; next != last; ) {
        int_swap(first++, next++);
        if (first == n_first) n_first = next;
        else if (next == last) next = n_first;
    }
}
 
void int_transpose(int* mat, int N, int M)
{
    int b_inc = N > M ? 1 : N;
    int n_inc = N > M ? M : 1;
    int* b = mat + 1;
    int* n = mat + M;
    for (; n < mat + N*M; b += b_inc, n += n_inc) {        
        int* first   = b < n ? b : n;
        int* n_first = b < n ? n : b;
 
        int_rotate(first, n_first, n_first + 1);
    }
}
 
int main(void)
{
    int mat[2][2] = {{1, 2}, {3, 4}};
 
    for (int n = 0; n < 2; n++) {
        for (int m = 0; m < 2; m++)
            printf("%d ", mat[n][m]);
        putchar('\n');
    }
    putchar('\n');
 
    int_transpose(&mat[0][0], 2, 2);
 
    for (int n = 0; n < 2; n++) {
        for (int m = 0; m < 2; m++)
            printf("%d ", *(&mat[0][0] + n*2 + m));
        putchar('\n');
    }
    putchar('\n');
 
    int_transpose(&mat[0][0], 2, 2);
 
    for (int n = 0; n < 2; n++) {
        for (int m = 0; m < 2; m++)
            printf("%d ", mat[n][m]);
        putchar('\n');
    }    
}

Код

3x2 http://ideone.com/3ItZB3
(лень копипастить)

4x2 http://ideone.com/Be9u6F

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

C

#include <stdio.h>
#include <stdlib.h>
 
void int_swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
 
void int_rotate(int* first, int* n_first, int* last)
{
    if (first == n_first) return;
    if (n_first == last) return;
 
    int* next = n_first;
    do {
        int_swap(first++, next++);
        if (first == n_first) n_first = next;
    } while (next != last);
 
    for (next = n_first; next != last; ) {
        int_swap(first++, next++);
        if (first == n_first) n_first = next;
        else if (next == last) next = n_first;
    }
}
 
void int_transpose(int* mat, int N, int M)
{
    int b_inc = N > M ? 1 : N;
    int n_inc = N > M ? M : 1;
    int* b = mat + 1;
    int* n = mat + M;
    for (; n < mat + N*M; b += b_inc, n += n_inc) {        
        int* first   = b < n ? b : n;
        int* n_first = b < n ? n : b;
 
        int_rotate(first, n_first, n_first + 1);
    }
}
 
int main(void)
{
    int mat[4][2] = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};
 
    for (int n = 0; n < 4; n++) {
        for (int m = 0; m < 2; m++)
            printf("%d ", mat[n][m]);
        putchar('\n');
    }
    putchar('\n');
 
    int_transpose(&mat[0][0], 4, 2);
 
    for (int n = 0; n < 2; n++) {
        for (int m = 0; m < 4; m++)
            printf("%d ", *(&mat[0][0] + n*4 + m));
        putchar('\n');
    }
    putchar('\n');
 
    int_transpose(&mat[0][0], 2, 4);
 
    for (int n = 0; n < 4; n++) {
        for (int m = 0; m < 2; m++)
            printf("%d ", mat[n][m]);
        putchar('\n');
    }    
}

Код

Код int_rotate списан с http://en.cppreference.com/w/c... ementation . Впрочем, здесь не нужна настолько общая реализация вращения. Функция int_rotate используется чтобы промежуток [a, b, c, ... , d, e] превратить в [e, a, b, c, ... , d]. Достаточно написать более понятную специальную функцию, реализующую данную перестановку.

Добавлено через 16 минут
Впрочем, код не работает *yawn*

Добавлено через 4 часа 12 минут
Так получше: http://ideone.com/AoBHbB

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

C

#include <stdio.h>
 
void int_swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
 
void int_rotate(int* first, int* n_first, int* last)
{
    if (first == n_first) return;
    if (n_first == last) return;
 
    int* next = n_first;
    do {
        int_swap(first++, next++);
        if (first == n_first) n_first = next;
    } while (next != last);
 
    for (next = n_first; next != last; ) {
        int_swap(first++, next++);
        if (first == n_first) n_first = next;
        else if (next == last) next = n_first;
    }
}
 
void int_transpose(int* mat, int N, int M)
{
    int dst = 1;
    int src = M;
    int old_src = src;
    int src_inc = M;
 
    while (src < N*M && dst < src) {
        int_rotate(mat + dst, mat + src, mat + src + 1);
 
        if ((dst+1) % N != 0) {
            dst += 1;
            src += src_inc;
        } else {
            dst += 2;
            src = old_src;
            src_inc -= 1;
            src += N - 1;
            old_src = src;
        }
    }
}
 
#define N 5
#define M 3
 
int main(void)
{
    int mat[N][M];
    for (int n = 0; n < N; n++)
        for (int m = 0; m < M; m++)
            mat[n][m] = n*M + m;
 
    for (int n = 0; n < N; n++) {
        for (int m = 0; m < M; m++)
            printf("%x ", mat[n][m]);
        putchar('\n');
    }
    putchar('\n');
 
    int_transpose(&mat[0][0], N, M);
 
    for (int n = 0; n < M; n++) {
        for (int m = 0; m < N; m++)
            printf("%x ", *(&mat[0][0] + n*N + m));
        putchar('\n');
    }
    putchar('\n');
}

Протестировал почти на всех комбинациях N×M от 1×1 до 5×5, для которых N*M <= 16;

Специалистам по теории групп оставляю оптимизацию алгоритма (или доказательство того, что он оптимален).

Добавлено через 16 часов 41 минуту

Сообщение от УГнетатель

Специалистам по теории групп оставляю оптимизацию алгоритма (или доказательство того, что он оптимален).

Алгоритм, кстати, крайне неоптимален. Для него число swap-ов для матрицы N×M равно в точности произведению (N-1)-го на (M-1)-й треугольных чисел: $https://www.cyberforum.ru/cgi-bin/latex.cgi?T_{N-1} \cdot T_{M-1}$ . Если подставить определение треугольных чисел, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac {N(N-1)} 2 \frac {M(M-1)} 2$ или $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac {N M (N-1) (M-1)} 4$ . Короче, число обменов растёт как $https://www.cyberforum.ru/cgi-bin/latex.cgi?\Theta \left( (N M)^2 \right)$ .

Вот таблица для некоторых малых размеров матриц. В таблице указано число обменов. Видно, что для матрицы 5×5 оно уже равно 100.
$https://www.cyberforum.ru/cgi-bin/latex.cgi? \begin{array}{r | c c c c } {}_M \backslash {}^N & 2 & 3 & 4 & 5 \\\hline 2 & 1 & 3 & 6 & 10 \\ 3 & 3 & 9 & 18 & 30 \\ 4 & 6 & 18 & 36 & 60 \\ 5 & 10 & 30 & 60 & 100 \end{array} $

Добавлено через 11 минут
Если вместо циклических сдвигов использовать только swap для элемента, стоящего не на своём месте с элементом, который должен быть на его месте, то тогда нужно гораздо меньше swap-ов. См. таблицу.

$https://www.cyberforum.ru/cgi-bin/latex.cgi? \begin{array}{r | c c c c } {}_M \backslash {}^N & 2 & 3 & 4 & 5 \\\hline 2 & 1 & 3 & 4 & 6 \\ 3 & 3 & 3 & 8 & 10 \\ 4 & 4 & 8 & 6 & 16 \\ 5 & 6 & 10 & 16 & 10 \end{array} $

Проблема в том, что для циклических перестановок алгоритм определения границ промежутка, который надо вращать, весьма прост.
А вот как реализовать оптимальный алгоритм — пока непонятно. Что интересно, даже изменение числа перестановок с ростом одной из размерностей матрицы при фиксированной другой немонотонно!

Байт · 19.08.2017, 09:26

УГнетатель, правильно ли я понял ваш алгоритм? (если неправильно, прошу прощения, смотрел ваш код вскользь)
В функции int_rotate для циклического сдвига на k позиций вы k раз делаете циклический сдвиг на 1 позицию. Это так, или мне показалось? Если действительно так, то можно существенно оптимизировать код. Если мне показалось, то еще раз прошу прощения.

@УГнетатель · 19.08.2017, 09:56

Байт, как я уже писал, реализация int_rotate слизана с std::rotate, с небольшими изменениями, связанными с тем, что я не возвращаю из int_rotate ничего. Похоже, что http://en.cppreference.com/w/c... ementation удовлетворяет требованиям к complexity, так что для int_rotate complexity должна быть такой же, как для std::rotate: линейной по размеру промежутка, который циклически сдвигается. Независимо от того, на какое число позиций производится сдвиг.

Оптимизации int_rotate отдельно тут не помогут. Оптимизировать надо весь алгоритм транспонирования с учётом того, что вращение используется только для того, чтобы поставить один элемент на правильное место (иногда на место встаёт более одного элемента, но это случается нечасто). Остальные элементы гоняются почём зря, ещё и по нескольку раз, т.к. вращаемые промежутки часто перекрываются.

Но, как я уже писал, закон нахождения места для вставки элемента и вставляемого элемента при использовании циклических сдвигов очень прост, в этом преимущество такого подхода.

Байт · 19.08.2017, 23:00

УГнетатель, имхо, весь алгоритм не должен быть сложнее, чем O(M*N)
Но я пока не вижу способа обойтись без вспомогательного массива битов.
Тут получаются циклические перестановки элементов, но надо знать, какие элементы матрицы уже переставлены.
Возможно, есть вполне определенный способ (математический) увидеть "корни" этих перестановок, но я его пока не нащупал.

@УГнетатель · 20.08.2017, 16:09

Байт, в общем, я прекратил попытки решить эту задачу более оптимально самостоятельно и полез в википедию. Там пишут, что наиболее оптимальные из известных алгоритмов работают за O(NM log (NM)). Причём, если я правильно понял, это с использованием дополнительной памяти.

Правда, http://www.netlib.org/utk/peop... talk35.pdf тут вроде как решают задачу за O(NM) при O(1) по памяти, переставляя в цикле. Я тоже нашёл приведённую там формулу вычисления следующего элемента цикла по текущему как "текущий*M mod (N*M - 1)". Только в случае, когда цикл замкнётся, т.е. мы получим начальный элемент цикла (например, единицу, если мы начали переставлять с единицы) не совсем понятно, как назначить следующий элемент в качестве "текущего", т.е начать другой цикл. Сколько я не бился, закономерностей не видно. Видимо, O(NM) при O(1) по памяти у авторов это при конкретном размере матрицы, когда нам известно число циклов и их начальные элементы. А в общем случае нужно сколько-то дополнительной памяти для того, чтобы проверять, что мы начинаем новый цикл, а не попадём в один из старых циклов.

Добавлено через 8 минут
http://on-demand.gputechconf.c... cesses.pdf тут O(N*M) при O(max(N,M)) доп. памяти. В принципе, неплохо.

@LFC · 20.08.2017, 19:16

попытался реализовать логику перебора массива не подряд,а по цепочке тех элементов которые должны меняться местами, arr[0][1] исходной матрицы переходит в arr[1][0] транспонированной матрицы,который соответствует arr[3] в одномерном массиве (или arr[0][3] исходной матрицы),значит следующим будет arr[3][0] транспонированной матрицы, который соответствует arr[9] в одномерном массиве (или arr[1][4] исходной матрицы), следующим будет arr[4][1] транспонированной матрицы, и т.д.
работает не на всех размерах(на четных,смешанных и больших не корректно) и нуждается в доработке

C

#include <stdio.h>
#define M 3
#define N 5
int main()
{
    int size = N * M, i = 0, j = 1, k = 1, count, arr[size], tmp1, tmp2;
    for(count = 0; count < size; count++){
        arr[count] = k++;
        if(count && !(count % N))
            putchar('\n');
        printf("%3d", arr[count]);
    }
    putchar('\n');
    putchar('\n');
    for(count = 0; count < size; count++)
        printf("%3d", arr[count]);
    for(count = 0; count < size - (N - M +1 ); count++){
        if(!count){
            tmp1 = arr[j * M + i];
            arr[j * M + i] = arr[i * N + j];
            arr[i * N + j] = arr[j * N + i];
        }
        else{
            tmp2 = arr[j * M + i];
            arr[j * M + i] = tmp1;
            tmp1 = tmp2;
        }
        k = j * M + i;
        if(k == N)
            k++;
        i = k / N;
        j = k % N;
    }
    putchar('\n');
    putchar('\n');
    for(count = 0; count < size; count++)
        printf("%3d", arr[count]);
    putchar('\n');
    putchar('\n');
    for(count = 0; count < size; count++){
        if(count && !(count % M))
            putchar('\n');
        printf("%3d", arr[count]);
    }
}

@Romadxd 0 / 0 / 0 Регистрация: 16.11.2016 Сообщений: 10
		1
	Выполнить операцию транспонирования прямоугольной матрицы A 16.08.2017, 10:14. Показов 3525. Ответов 30 Метки нет (Все метки) Выполнить операцию транспонирования прямоугольной матрицы A(m,n),m<>n , не выделяя дополнительного массива для хранения результата. Матрицу представить в виде одномерного массива. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	16.08.2017, 11:17	2
	Romadxd, Есть ли какие-нибудь собственные попытки, наброски? Хотя бы скелет программы? 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	16.08.2017, 22:09	5
	JohnyWalker, mid150, А вы это видели? Сообщение от Romadxd Матрицу представить в виде одномерного массива. И задача - пустяк. Небольшая игра с индексами, которая лично мне не прибавит ума. А вам может быть и интересна, и забавна. Добавлено через 2 минуты А вот заголовок темы Линейная алгебра и впрямь наводит на грустные мысли... 0

@mid150 41 / 38 / 22 Регистрация: 02.04.2016 Сообщений: 131
	17.08.2017, 06:47	6
	Байт, мне думается, что нужно представлять в виде одномерного массива уже транспонированную матрицу, то есть ту, что получаем на выходе, то есть просто строка из символов входящих в матрицу. Если очень нужно, можно объявить таковой массив,заполнить его, а только потом выводить. Однако, так как одномерный массив в программе более негде не фигурирует, кроме как на выводе, то особого смысла в его объявлении я не вижу. 0

@JohnyWalker 200 / 87 / 9 Регистрация: 15.11.2010 Сообщений: 472
	17.08.2017, 09:23	7
	Сообщение от Байт JohnyWalker, mid150, А вы это видели? Сообщение от Romadxd Матрицу представить в виде одномерного массива. Нет, этого я не заметил. Иначе не написал бы свой пост №3. Действительно можно взять одномерный массив размерностью MN и рассматривать его и как двумерный [M][N], и как двумерный [N][M]. И задача - пустяк. Небольшая игра с индексами, которая лично мне не прибавит ума. А вам может быть и интересна, и забавна. Тут ведь, как я понимаю, нужно взять этот массив с исходной матрицей и в него же записать транспонированную матрицу. То есть один и тот же буфер используется и для хранения исходной матрицы, и для записи в него результата транспонирования. Промежуточного буфера использовать нельзя. Начнёшь просто перезаписывать строки как столбцы — затрёшь часть чисел исходной матрицы и получишь неправильный результат. Мне вот в голову не приходит простого решения, как это можно сделать. И числа переставить в массиве, и исходные числа не затереть в процессе перестановки. Добавлено через 58 минут* В общем, Байт, условие задачи понятно (оно вполне корректно после твоего уточнения), а как решить её, я не знаю. Сходу простого решения в голову не приходит. 1

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	17.08.2017, 21:36	10
	JohnyWalker, да, вы правы. Погорячился я. Не так все просто. И работа вами проделана большая. По поводу двойного транспонирования - мой несомненный ляп. Но вот тут Сообщение от JohnyWalker к прямоугольной не квадратной матрице, хотя в этом смысла особого нет. имхо, вы не правы Вот матрица (строка) ( 1, 2) Вот она же транспонированная (столбец) 1 2 Самая обычная математическая операция. Часто используемая. Сейчас нет особого настроения и времени, но обещаю заняться этим вопросом и свою ошибку исправить в ближайшее время Добавлено через 17 минут JohnyWalker, Посмотрел на примере 2 х 3 1 2 3 4 5 6 Линейная запись 1 2 3 4 5 6 Транспонированная 1 4 2 5 3 6 Линейная запись 1 4 2 5 3 6 Любопытная перестановка. Закон пока не улавливается. Думать надо. 1

@JohnyWalker 200 / 87 / 9 Регистрация: 15.11.2010 Сообщений: 472
	17.08.2017, 21:39	11
	Сообщение от Байт Но вот тутимхо, вы не правы Вот матрица (строка) ( 1, 2) Вот она же транспонированная (столбец) 1 2 Там структура всего этого сложная и запутанная. Квадратная матрица симметричная (в смысле равенства своих сторон, а не в том смысле, что под этим понимают в линейной алгебре, конечно), и исходная, и результирующая транспонированная матрица естественно ложатся друг на друга. Поэтому простейший алгоритм и работает. А вот когда матрица прямоугольная, но не квадратная, и при этом обе матрицы с противоположным значением размеров должны находиться в одном буфере, не ложатся они так легко друг на друга. При их наложении возникает путаница и полное несоответствие одного другому. Поэтому и не проходит этот алгоритм в такой простой форме. Вы можете попробовать решить эту задачу, но это явно головоломка. Я с ней не стал разбираться, она не такая простая. На решение таких головоломок может уйти и месяц, и никакой гарантии, что до него додумаешься. И при этом практической пользы в задаче никакой. Может, она и очень просто решается, может, и нет. В общем, это головоломка на перестановки элементов. Сам этим не хочу заниматься. Вы можете попробовать чисто из спортивного интереса, не более. 2

Байт
	17.08.2017, 21:42 #12
	Не по теме: Сообщение от JohnyWalker тутимхо Хорошее слово получилось, не правда ли?:) 1

@JohnyWalker 200 / 87 / 9 Регистрация: 15.11.2010 Сообщений: 472
	17.08.2017, 21:43	13
	Сообщение от Байт 1 2 3 4 5 6 Линейная запись 1 2 3 4 5 6 Транспонированная 1 4 2 5 3 6 Линейная запись 1 4 2 5 3 6 Любопытная перестановка. Закон пока не улавливается. Думать надо. А впрочем, если задача вам нравится с чисто математической стороны, попробуйте из любви к искусству. Почему бы и нет Ха... В приведённом вами примере закон как раз есть. Приглядитесь ближе Только как его использовать... 1

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	18.08.2017, 10:03	14
	Немного подумав, пришел к таким выводам. Пусть матрица A[N][M] представлена в линейной записи C[NM]. Напечатать как матрицу А, так и матрицу транспонированную - тривиальная задача. Столь же тривиальна задача - создать линейное представление D[MN] транспонированной матрицы (в другой области памяти) Задача существенно усложняется, если запрещается использование дополнительной памяти. И дело здесь не в вычислении линейного индекса на основе двойного, а в необходимости производить циклические перестановки довольно замысловатого вида. Возможно, в решении этой задачи могла бы оказать помощь и Алгебра (Теория Групп, например) Я все-таки не оставляю надежды, разобраться с этой задачей.... 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	19.08.2017, 09:26	16
	УГнетатель, правильно ли я понял ваш алгоритм? (если неправильно, прошу прощения, смотрел ваш код вскользь) В функции int_rotate для циклического сдвига на k позиций вы k раз делаете циклический сдвиг на 1 позицию. Это так, или мне показалось? Если действительно так, то можно существенно оптимизировать код. Если мне показалось, то еще раз прошу прощения. 0

@УГнетатель 17 / 16 / 3 Регистрация: 18.08.2017 Сообщений: 54
	19.08.2017, 09:56	17
	Байт, как я уже писал, реализация int_rotate слизана с std::rotate, с небольшими изменениями, связанными с тем, что я не возвращаю из int_rotate ничего. Похоже, что http://en.cppreference.com/w/c... ementation удовлетворяет требованиям к complexity, так что для int_rotate complexity должна быть такой же, как для std::rotate: линейной по размеру промежутка, который циклически сдвигается. Независимо от того, на какое число позиций производится сдвиг. Оптимизации int_rotate отдельно тут не помогут. Оптимизировать надо весь алгоритм транспонирования с учётом того, что вращение используется только для того, чтобы поставить один элемент на правильное место (иногда на место встаёт более одного элемента, но это случается нечасто). Остальные элементы гоняются почём зря, ещё и по нескольку раз, т.к. вращаемые промежутки часто перекрываются. Но, как я уже писал, закон нахождения места для вставки элемента и вставляемого элемента при использовании циклических сдвигов очень прост, в этом преимущество такого подхода. 2

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	19.08.2017, 23:00	18
	УГнетатель, имхо, весь алгоритм не должен быть сложнее, чем O(M*N) Но я пока не вижу способа обойтись без вспомогательного массива битов. Тут получаются циклические перестановки элементов, но надо знать, какие элементы матрицы уже переставлены. Возможно, есть вполне определенный способ (математический) увидеть "корни" этих перестановок, но я его пока не нащупал. 0

@УГнетатель 17 / 16 / 3 Регистрация: 18.08.2017 Сообщений: 54
	20.08.2017, 16:09	19
	Байт, в общем, я прекратил попытки решить эту задачу более оптимально самостоятельно и полез в википедию. Там пишут, что наиболее оптимальные из известных алгоритмов работают за O(NM log (NM)). Причём, если я правильно понял, это с использованием дополнительной памяти. Правда, http://www.netlib.org/utk/peop... talk35.pdf тут вроде как решают задачу за O(NM) при O(1) по памяти, переставляя в цикле. Я тоже нашёл приведённую там формулу вычисления следующего элемента цикла по текущему как "текущийM mod (NM - 1)". Только в случае, когда цикл замкнётся, т.е. мы получим начальный элемент цикла (например, единицу, если мы начали переставлять с единицы) не совсем понятно, как назначить следующий элемент в качестве "текущего", т.е начать другой цикл. Сколько я не бился, закономерностей не видно. Видимо, O(NM) при O(1) по памяти у авторов это при конкретном размере матрицы, когда нам известно число циклов и их начальные элементы. А в общем случае нужно сколько-то дополнительной памяти для того, чтобы проверять, что мы начинаем новый цикл, а не попадём в один из старых циклов. Добавлено через 8 минут http://on-demand.gputechconf.c... cesses.pdf тут O(N*M) при O(max(N,M)) доп. памяти. В принципе, неплохо. 1