Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Транспонирование матрицы

Автор: Alagert 8.1.2006, 14:30

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

Погите плиз разобраться с этой задачей, очень нужно!
Всем спасибо!

Автор: maxim1000 8.1.2006, 15:22

ну, например, так:
идем по массиву
смотрим на очередной элемент массива
ищем в массиве то значение, которое там должно быть
меняем их друг с другом
идем дальше...

пример:
матрица 2х3 (в одномерном представлении): 1, 2, 3; 4, 5, 6
1-й шаг: смотрим на первый элемент - это (1,1) его не надо менять (так всегда будет на первом шаге)
2-й шаг: смотрим на второй элемент - это (1,2): там стоит 2, а должно быть 4, меняем их местами
и так далее

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

Автор: Illuminaty 8.1.2006, 15:25

а - массив [0..n], где n = m*m - 1, где m - размерность матрицы
temp - переменная
транспонирование:

Код

for (i = 0; i < n; i ++) {
  for (j = 0; j < i - 1; j++) {
    temp = a[i*n + j];
    a[i*n + j] = a[j*n + i];
    a[j*n + i] = temp;
  }
}

Автор: Alagert 8.1.2006, 16:42

Цитата(Illuminaty @ 8.1.2006, 15:25)

а - массив [0..n], где n = m*m - 1, где m - размерность матрицы
temp - переменная
транспонирование:

Код

for (i = 0; i < n; i ++) {
  for (j = 0; j < i - 1; j++) {
    temp = a[i*n + j];
    a[i*n + j] = a[j*n + i];
    a[j*n + i] = temp;
  }
}

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

Автор: Illuminaty 8.1.2006, 16:53

Alagert, двойку тебе по алгебре в зачетку поставить надо smile

Прямоугольные матрицы не транспонируются

Автор: Alagert 8.1.2006, 17:00

Цитата(Illuminaty @ 8.1.2006, 16:53)

Alagert, двойку тебе по алгебре в зачетку поставить надо smile

Прямоугольные матрицы не транспонируются

У меня 5 по матану за все курсы smile

Прямоугольная матрица замечательно траспонируется! Была матрица MxN, а стала NxM.
Прямоугольные матрицы не обращаются(если не рассматривать случай псевдообратных матриц)

Автор: Illuminaty 8.1.2006, 17:28

Цитата(Alagert @ 8.1.2006, 18:00

)

У меня 5 по матану за все курсы

Тогда и флаг тебе в руки smile

Автор: Illuminaty 8.1.2006, 17:54

Признаю ошибку. Мои 5 по алгебре остались в прошлом веке. Действительно, перепутал с обратными... Позор на мою седую голову... Ладно хоть преподаватель не видит по алгебре - его бы удар хватил smile

В связи с этим помогу с алгоритмом, но через некоторое время...

Автор: Alagert 8.1.2006, 18:28

Цитата(Illuminaty @ 8.1.2006, 17:54)

В связи с этим помогу с алгоритмом, но через некоторое время...

Всем свойственно ошибаться. Огромное спасибо за обещание помочь.

Автор: Mal Hack 8.1.2006, 19:34

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

Код

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
 mm : array[1..10] of array[1..10] of integer;
 c,n,m,i,j:integer;
 per : boolean = false;
begin
 n := 4;
 m := 1;

 for i := 1 to n do
  begin
   for j := 1 to m do
    begin
     mm[i,j] := random(10);
     write( mm[i,j]: 4 );
    end;
   writeln;
  end;

 writeln;

 if n > m then
  begin
   c := n;
   n := m;
   m := c;
   per := true;
  end;

 for i := 1 to n do
  for j := i + 1 to m do
   begin
    c := mm[i,j];
    mm[i,j] := mm[j,i];
    mm[j,i] := c;
   end;

 if per = true then
  begin
   c := n;
   n := m;
   m := c; 
  end;

 for i := 1 to m do
  begin
   for j := 1 to n do
    write( mm[i,j]: 4 );

   writeln;
  end;


 readln; 
end.

Автор: Illuminaty 8.1.2006, 20:09

Mal Hack, прочитай условие внимательно

Цитата(Alagert @ 8.1.2006, 15:30

)

Матрица записана построчно в одномерный массив.

Автор: Mal Hack 8.1.2006, 20:42

Illuminaty массив массива строк. Или имеется ввиду вектор?

Автор: Alagert 8.1.2006, 20:45

Цитата(Mal Hack @ 8.1.2006, 20:42)

Illuminaty массив массива строк. Или имеется ввиду вектор?

Для простоты есть интовый массив размерности m*n, туда построчно записана вся матрица.

Автор: maxim1000 8.1.2006, 20:56

хм... в том, что я предложил, ошибочка...
иногда будет получаться, что число для замены надо взять из уже "отсортированой" части, а значит, что там будут не те числа, которые были изначально...

Автор: Mal Hack 8.1.2006, 21:36

Работает когда m > n, щас думаю над обратным случаем...

Код

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
 mm : array[1..50] of integer;
 c,n,m,i,j:integer;
begin
 n := 3;
 m := 3;
 
 for i := 1 to n do
  begin
   for j := 1 to m do
    begin
     mm[(i-1)*m+j] := random(10);
     write( mm[(i-1)*m+j]: 4 );
    end;
   writeln;
  end;

 writeln;

 for i := 1 to n do
  for j := i + 1 to m do
   begin
    c := mm[(i-1)*m+j];
    mm[(i-1)*m+j] := mm[i+(j-1)*m];
    mm[i+(j-1)*m] := c;
   end;

 for i := 1 to m do
  begin
   for j := 1 to n do
    write( mm[(i-1)*m+j]: 4 );

   writeln;
  end;


 readln; 
end.

Автор: Mal Hack 8.1.2006, 22:01

Alagert уточни в каком именно виде и как хранится матрица, и в каком ее надо записать.

Автор: Alagert 8.1.2006, 22:54

Матрица записана след образом:

Код


int * matrix =new int[m*n];

//for example
for(int=0;i<m*n;i++) matrix[i]=i;

т.е была матрица: 1 2 3
4 5 6

записана в массив будет в виде : 1 2 3 4 5 6
после траспонирования: 1 4
2 5
3 6
в массиве будет: 1 4 2 5 3 6

Пасибо за вариант, ща буду его разбирать.

Автор: Akina 8.1.2006, 23:20

Алгоритм:
Исходная матрица - A (M,N) в векторе V (M*N)
Конечная матрица - B (N,M)
Возьмем элемент вектора V(K).
В исходной матрице его адрес:
A (K mod N, K div N)
В конечной матрице его адрес должен стать:
B (K div N, K mod N)
Т.е. в векторе V его адрес станет
V( N*(K mod N) + (K div N))

Итого:

Код


For K = 0 to M*N
   If K > (N*(K mod N)+(K\N)) Then
      ' Менять местами надо только один раз
      ' Диагональные - вообще не надо
      SWAP V(K), V(N*(K mod N)+(K\N))
   End if
Next

PS. Писано на коленке, проверьте.

Автор: Alagert 8.1.2006, 23:58

Цитата(Akina @ 8.1.2006, 23:20)

Код


For K = 0 to M*N
   If K > (N*(K mod N)+(K\N)) Then
      ' Менять местами надо только один раз
      ' Диагональные - вообще не надо
      SWAP V(K), V(N*(K mod N)+(K\N))
   End if
Next

PS. Писано на коленке, проверьте.

Работает, если исправить кое что:
1) возьмем V(K), в исходной матр это будет A(K/N, k mod N)
2) в траспонированной B(K mod N, K/N)
3) перестановка в векторе V(M*(K mod N) + K/N)

Вот вроде так. В твоем варианте получается, что траспонирование матр никак не зависит от ее второй размерности.

2 Mal Hack
В коде, который ты привел ошибка: ты выходишь за границы массива, когда меняешь элементы. И ты принял, что матр квадратная.

Ща еще потестирую.
ВСЕМ БОЛЬШОЕ СПАСИБО!

Автор: Illuminaty 9.1.2006, 01:11

На тот случай если алгоритм Akina не сработал привожу полную рабочую программу.

Код

program MatrixTransp;
{$APPTYPE CONSOLE}
uses
  SysUtils;

var
  N: Integer; // по вертикали
  M: Integer; // по горизонтали
  a: array of Integer; // наш массив
  maxmodul: Integer; // максимальный модуль для пометки элемента массива
  temp_a, temp_i, i, j: Integer; // временные переменные

procedure InitArray;
var
  i, j: Integer; // счетчик
begin
{инициируем размерность матрицы и заполняем случайными числами от -50 до 50}
  Write('Введите N ');
  Read(N);
  Write('Введите M ');
  Read(M);
  SetLength(a, M*N);
  Randomize;
  for i := 0 to M*N - 1 do
    a[i] := Random(100) - 50;
{Выведем матрицу}
  for i:= 0 to N-1 do
  begin
    for j:= 0 to M-1 do
      Write(a[i*M + j]: 4);
    writeLn;
  end;
end;

procedure FindMaxModule;
{находим максимальное по модулю число и записываем его модуль в maxmodule}
var
  i: Integer; // счетчик
begin
  maxmodul := a[0];
  for i := 0 to M*N - 1 do
    if maxmodul < abs(a[i]) then
      maxmodul :=  abs(a[i]);
end;

procedure Mark(i: Integer);
{"помечаем" элемент массива, путем увеличения его по модулю на maxmodul + 1}
begin
  if a[i] >= 0 then
    a[i] := a[i] + maxmodul + 1
  else
    a[i] := a[i] - maxmodul - 1;
end;

procedure Remark(i: Integer);
{"размечаем" элемент массива, путем уменьшения его по модулю на maxmodul + 1}
begin
  if a[i] >= 0 then
    a[i] := a[i] - maxmodul - 1
  else
    a[i] := a[i] + maxmodul + 1;
end;

function isMark(i: Integer): Boolean;
{возвращает true, если элемент "помечен" и false в противном случае}
begin
  Result := abs(a[i]) > maxmodul;
end;

function TransPos(i: Integer): Integer;
{получение номера в массиве, по которому лежит транспонированный эллемент}
begin
  Result := (i mod n) * m + (i div n);
end;

begin
  InitArray;
  FindMaxModule;

  for i := 0 to N*M - 1 do
  begin
    if not isMark(i) then // если с элементом раньше не работали
    begin
      temp_i := i;
      while not isMark(TransPos(temp_i)) do begin
        {обмен значениями}
        temp_a := a[TransPos(temp_i)];
        a[TransPos(temp_i)] := a[temp_i];
        a[temp_i] := temp_a;
        {помечаем элемент}
        Mark(temp_i);
        temp_i := TransPos(temp_i);
      end;
    end;
  end;

  {размечаем все меченные элементы}
  for i := 0 to N*M - 1 do
  begin
    if isMark(i) then
      Remark(i);
  end;


// выведем транспонированную матрицу
  writeLn;
  for i:= 0 to M-1 do
  begin
    for j:= 0 to N-1 do
      Write(a[i*N + j]: 4);
    writeLn;
  end;

  readln;
  readln;
end.

Автор: maxim1000 9.1.2006, 01:49

Цитата

В исходной матрице его адрес:
A (K mod N, K div N)
В конечной матрице его адрес должен стать:
B (K div N, K mod N)
Т.е. в векторе V его адрес станет
V( N*(K mod N) + (K div N))

проблема в том, что тот элемент, на место которого нужно поставить K-й, необязательно должен стать на его место...
пример:
исходная матрица - 2 строки, 3 столбца
0 1 2 3 4 5
переходит в
0 3 1 4 2 5

например, 1 становится на место 2, но не наоборот...

P.S. если не ошибся... smile

Автор: Illuminaty 9.1.2006, 02:07

Почему не будет работать алгоритм Akina.
Потому что при транспонировании прямоугольной матрицы элементы не будут заменятся двунаправленно. Т.е. пусть у нас есть матрица:
┌─┬─┬─┐
│0│1│2│
├─┼─┼─┤
│3│4│5│
└─┴─┴─┘, она транспонируется в матрицу
┌─┬─┐
│0│3│
├─┼─┤
│1│4│
├─┼─┤
│2│5│
└─┴─┘, если все записать в строку, то получим, что была строка [0, 1, 2, 3, 4, 5], получили транспонированием строку [0, 3, 1, 4, 2, 5]. Т.е. преобразовния следующие
0 -> 0;
1 -> 2 -> 4 -> 3 -> 1;
5 -> 5;
В зависимости от размерности матрицы может быть разное количество таких цепочек.
при реализации этих преобразований нужно запомнить, с какими элементами производили преобразования, а с какими - нет. Для этого в моем решении вводится переменная maxmodul, которая хранит максимальный модуль из входной матрицы. Элемент, с которым происвели преобразование, помечаем путем увеличения его модуля на maxmodul + 1. В конце работы, для всех помеченных элементов модуль уменьшаем на maxmodul + 1.
Добавлено @ 02:08
maxim1000 немного раньше это написал. Да еще и с тем же примером, что и у меня

Автор: maxim1000 9.1.2006, 02:22

Цитата

Для этого в моем решении вводится переменная maxmodul, которая хранит максимальный модуль из входной матрицы. Элемент, с которым происвели преобразование, помечаем путем увеличения его модуля на maxmodul + 1.

это тоже, как мне кажется, не подходит - при больших значениях оно будет приводить к переполнению операций сложения...
на самом деле, это почти эквивалентно использованию старших битов значений...

Автор: Illuminaty 9.1.2006, 02:31

maxim1000, можно и тип Real (или double) сделать. Я просто думал над пометкой без использования дополнительных массивов. Насчет переполнения я тоже думал, но ничего другого не придумал. Времени на это не было. И так программу накидал - должен был, а то лопухнулся с определениями. Ладно хоть Alagert не расскажет моему преподавателю по алгебре как лопухнулся. smile

Во всяком случае, программа работает smile

Если кто придумает как лучше помечать элементы - милости прошу. Только функции изменить и вперед!

Автор: maxim1000 9.1.2006, 02:40

Цитата

Если кто придумает как лучше помечать элементы - милости прошу

помечать элементы никак нельзя - нельзя заставить матрицу хранить больше информации, чем то, насколько она расчитана
в случае с double произойдет потеря точности...
так что получится ненастоящее транспонирование...
Добавлено @ 02:45
вот пришел в голову еще один способ:
(для начала сразу скажу - первый индекс - строка или количество строк, второй - столбец или количество столбцов)
наша задача - транспонировать матрицу m*n
мы точно знаем, какие элементы будут в конце массива - нужно просто взять последний столбец и вытащить его элементы в конец
дальше можно отбросить последние m элементы и обработать (n-1)*m матрицу, которая задана в оставшейся части массива...

Автор: Illuminaty 9.1.2006, 02:47

Цитата(maxim1000 @ 9.1.2006, 03:40

)

помечать элементы никак нельзя

но у меня же получился один вариант smile

Можно, кстати, перевести в строковый тип и помечать добавлением какого-нибудь символа (или группы символов)
Добавлено @ 02:50

Цитата(maxim1000 @ 9.1.2006, 03:40

)

вот пришел в голову еще один способ:

, а те элементы, что в конце, ты куда денешь? smile

У этого способа та же проблема...

Автор: maxim1000 9.1.2006, 02:58

Код


void Transpose(int *Array,unsigned int RowCount,unsigned int ColumnCount)
{
  while(ColumnCount>1)
  {
    //draw last column into the tail of the array
    //(begin from the bottom)
    for(unsigned int c=0;c<RowCount;c++)
    {//draw (ColumnCount-1,RowCount-1-c)-th element to the end
      unsigned int index=ColumnCount-1+ColumnCount*(RowCount-1-c);
      unsigned int target=ColumnCount*RowCount-1-c;
      int temp=Array[index];
      for(i=index;i<target;++i)
        Array[i]=Array[i+1];
      Array[target]=temp;
    }
    //proceed with smaller matrix
    --ColumnCount;
  }
}

вот...
правда, тоже писалось на коленках smile

Добавлено @ 03:02

Цитата(Illuminaty @ 9.1.2006, 02:47

)

но у меня же получился один вариант

который решает задачу только для некоторых матриц (у которых не слишком большие элементы)

Цитата(Illuminaty @ 9.1.2006, 02:47

)

Можно, кстати, перевести в строковый тип и помечать добавлением какого-нибудь символа (или группы символов)

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

Цитата(Illuminaty @ 9.1.2006, 02:47

)

а те элементы, что в конце, ты куда денешь?

они сдвинутся
под "вытаскиванием" элементов я имел в виду такую операцию - берем элемент, все, которые после него, сдвигаем в сторону начала массива (занимая освободившееся место), а взятый элемент - в конец массива (ну или на каком-то расстоянии от конца)
Добавлено @ 03:08
пример с матрицей 2*3
1 2 3 4 5 6
1. вытаскиваем элементы последнего столбца (3 и 6) в конец массива (начиная с нижних)
1.1. вытаскиваем 6 - его вытаскивать не надо, так тут ничего и делать не надо
1.2. вытаскиваем 3:
3 запоминаем (одна временная переменная)
1 2 3 4 5 6 -> 1 2 4 5 (неважно что) 6 -> 1 2 4 5 3 6
Добавлено @ 03:11
а теперь сводим задачу (2*3) к задаче (2*2), уменьшая количество столбцов и размер массива (точнее, размер той части массива, с котороймы работаем), т.е. транспонируем матрицу 2*2: 1 2 4 5
по тому же алгоритму

Автор: Mayk 9.1.2006, 09:29

А если менять цепочкой, а не линейно?

То есть берем i-ый элемент и ставим его на корректное место j.
После этого мы берем не (i+1) элемент(как не единожды предлагалось ранее), а элемент j (то есть тот, на котором должен стоять i).
Если же такого уже нет, то берем i+1.
При этом i+1 считается обработанным, если в обходе его цепочки мы натолкнемся на обработанный элемент.

Цепочка - это...

Пример:

Есть
123
456

(123456)

Хотим

14
25
36

(142536)

Отображение A->At такое:
1->1, 2->3, 3->5, 4->2, 5->4, 6->6

Цепочка - это вот такая ерунда: 1->1, 2->3->5->4->2 ну и прочее. Блин. Не могу сформулировать, но интуитивно надеюсь понятно.

Запускаем алгоритм:
1) Берем i=1. (123456 <- текущий массив)
2) 1->1. Единица уже была(только что), не меняем (123456)
3) Берем 2. Ставим её на 3. 3 запоминаем (122456)
4) Ставим 3 на 5. 5 запомиаем (122436)
5) Ставим 5 на 4. 4 запоминаем(122536)
6) Ставим 4 на 2. мы начинали с двойки, поэтому останавливаемсч(142536)

7) Берем 3. Мы её не будем трогать, так как цепочка 3->5->4->2 приводит к уже обработанной 2.(142536)
8) Берем 4. Не меняем, так как 4->2 приводит к обработанной 2(142536)
9) Берем 5. Не меняем, так как 5->4 приводит к обработанной 4(142536)
10) Берем 6. Не меняем, так как 6->6 приводит к обработываемой 6(142536)

Готово. 142536

Попробую обосновать инвариантом цикла,

Инвариант цикла -
цепочки всех элементов до текущего оттранспорированны.

Инициализация - текущего элемента нет.
Предшественников нет. (ну или даже 1-ый элемент всегда оттранспорирован)
Сохранения инварианта - мы меняем местами только те элементы, цепочки которых не содержат
предшествующих элементов. Иными словами если что-то было верно, то оно останется верным.
Если что-то было неверным, оно станет верным. Мы трогаем лишь элементы цепочки.
Завершение - Все цепочки оттранспорированны. => оттранспорированны ВСЕ элементы матрицы .

ЗЫ. Цепочка образует цикл, это всё очень имхо и это я не доказывал, но имхо это так. Все таки A=Att.
Добавлено @ 09:34
Тьфу блин, как же я это такой пост пропустил.
Идея с цепочками уже была у Illuminaty
Ну ладно. По крайне мере можете попниать обоснование.

Автор: Illuminaty 9.1.2006, 10:38

maxim1000, круто! Проверил - действительно работает.
Только твоя функция немного неправильно работает, но это из-за

Цитата(maxim1000 @ 9.1.2006, 03:58

)

тоже писалось на коленках

.
Вот полностью работающая программа

Код

program MatrixTransp;
{$APPTYPE CONSOLE}
uses
  SysUtils;

var
  N: Integer; // по вертикали
  M: Integer; // по горизонтали
  a: array of Integer; // наш массив
  maxmodul: Integer; // максимальный модуль для пометки элемента массива
  i, j: Integer; // временные переменные

procedure InitArray;
var
  i, j: Integer; // счетчик
begin
{инициируем размерность матрицы и заполняем случайными числами от -50 до 50}
  Write('Введите N ');
  Read(N);
  Write('Введите M ');
  Read(M);
  SetLength(a, M*N);
  Randomize;
  for i := 0 to M*N - 1 do
    a[i] := Random(100) - 50;
{Выведем матрицу}
  for i:= 0 to N-1 do
  begin
    for j:= 0 to M-1 do
      Write(a[i*M + j]: 4);
    writeLn;
  end;
end;

procedure Transpose;
var
  i, j, temp, c, k: Integer;
begin
  k := 0;
  for j := M -1 downto 0 do
    for i := N -1 downto 0 do
    begin
      temp := a[i*(j+1) + j];
      for c := i*(j+1) + j to M*N - k - 2 do
        a[c] := a[c+1];
      a[M*N - k - 1] := temp;
      k := k + 1;
    end;
end;


begin
  InitArray;
  Transpose;
// выведем транспонированную матрицу
  writeLn;
  for i:= 0 to M-1 do
  begin
    for j:= 0 to N-1 do
      Write(a[i*N + j]: 4);
    writeLn;
  end;

  readln;
  readln;
end.

Проверено - работает

Автор: Alagert 9.1.2006, 11:31

Всем огромное спасибо! А я вот вчера в 1.30 уже сломался. Проверил вариант Akina и бухнулся спать.
Сейчас буду разбирать все ваши идеи.

Автор: Alagert 9.1.2006, 13:07

Всем огромное спасибо!
2 maxim1000 Спасибо за алг! Все работает. Сам думал сводить задачу к меньшей размерности, но до твоего варианта так и не додумался!

12 числа покажу преподу, реакцию отпишу. Может есть еще легче вариант!

Автор: maxim1000 9.1.2006, 15:46

Цитата(Mayk @ 9.1.2006, 09:29

)

Тьфу блин, как же я это такой пост пропустил.
Идея с цепочками уже была у Illuminaty
Ну ладно. По крайне мере можете попниать обоснование.

а, наверное, и не стоит пинать smile

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

Автор: Alagert 12.1.2006, 21:52

Я показал преподу это решение! Он был удивлен, что все это так просто работает! Говорит, что я чего мухлюю! Я рассказал про вариант с цепочками, он сказал, что это гиблое дело. И из этого нормальный алгоритм не выйдет!

ЗЫ Может подскажете как автаматически оттестировать этот алг?

Автор: Illuminaty 12.1.2006, 22:05

возьми мой код
откомпилируй его при преподе
запусти и пусть он введет свои данные

А на самом деле составь хорошо оформленное математическое доказательство, но это уже в другой раздел..

Автор: myxacuk 16.4.2016, 20:32

Модератор: Сообщение скрыто.