Рубрики

Inplace (фиксированное пространство) M x N размер матрицы транспонировать | обновленный

Около четырех месяцев разрыва (отсутствует GFG), новый пост. Учитывая матрицу M x N, транспонируйте матрицу без вспомогательной памяти. Матрицу легко транспонировать, используя вспомогательный массив. Если матрица имеет симметричный размер, мы можем транспонировать матрицу на месте, отразив 2D-массив по диагонали (попробуйте сами). Как транспонировать матрицу произвольного размера на месте? Смотрите следующую матрицу,

a b c       a d g j
d e f  ==>  b e h k
g h i       c f i l
j k l

Согласно двумерной нумерации в C / C ++, соответствующее отображение местоположения выглядит так:

Org element New
 0     a     0
 1     b     4
 2     c     8
 3     d     1
 4     e     5
 5     f     9
 6     g     2
 7     h     6
 8     i    10
 9     j     3
 10    k     7
 11    l    11

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

  • 1-> 4-> 5-> 9-> 3-> 1 — Всего 5 элементов образуют цикл
  • 2-> 8-> 10-> 7-> 6-> 2 — еще 5 элементов образуют цикл
  • 0 — Сам цикл
  • 11 — Сам цикл

Из приведенного выше примера мы можем легко разработать алгоритм для перемещения элементов по этим циклам. Как мы можем генерировать циклы перестановок? Количество элементов в обеих матрицах является постоянным, определяемым как N = R * C, где R — количество строк, а C — количество столбцов. Элемент в местоположении ol (старое местоположение в матрице R x C), перемещенный в nl (новое местоположение в матрице C x R). Нам нужно установить связь между ol, nl, R и C. Предположим, что ol = A [или] [oc] . В C / C ++ мы можем рассчитать адрес элемента как,

ol = or x C + oc (ignore base reference for simplicity)

Он должен быть перемещен в новое место nl в транспонированной матрице, скажем, nl = A [nr] [nc] или в терминах C / C ++

nl = nr x R + nc (R - column count, C is row count as the matrix is transposed)

Обратите внимание, nr = oc и nc = or , поэтому заменив их на nl ,

nl = oc x R + or -----> [eq 1]

Решив соотношение между ol и nl , получим

ol     = or x C     + oc
ol x R = or x C x R + oc x R
       = or x N     + oc x R    (from the fact R * C = N)
       = or x N     + (nl - or) --- from [eq 1]
       = or x (N-1) + nl

ИЛИ,

nl = ol x R - or x (N-1)

Обратите внимание, что значения nl и ol никогда не выходят за пределы N-1 , поэтому, учитывая деление по модулю с обеих сторон на ( N-1 ), мы получаем следующее на основе свойств конгруэнтности:

nl mod (N-1) = (ol x R - or x (N-1)) mod (N-1)
             = (ol x R) mod (N-1) - or x (N-1) mod(N-1)
             = ol x R mod (N-1), since second term evaluates to zero
nl = (ol x R) mod (N-1), since nl is always less than N-1

Любопытный читатель, возможно, заметил значение вышеуказанного отношения. Каждое местоположение масштабируется с коэффициентом R (размер строки). Из матрицы очевидно, что каждое местоположение смещается на масштабный коэффициент R. Фактический множитель зависит от класса конгруэнции (N-1), то есть множитель может быть как -ve, так и + ve значением конгруэнтного класса. Следовательно, каждое преобразование местоположения является простым делением по модулю. Эти деления по модулю образуют циклические перестановки. Нам нужна некоторая информация для ведения учета уже перемещенных элементов. Вот код для преобразования матрицы на месте,

// Программа для транспонирования матрицы на месте
#include <stdio.h>
#include <iostream>
#include <bitset>
#define HASH_SIZE 128

  

using namespace std;

  
// Утилита для печати двумерного массива размером nr x nc и базовым адресом A

void Print2DArray(int *A, int nr, int nc)

{

    for(int r = 0; r < nr; r++)

    {

        for(int c = 0; c < nc; c++)

            printf("%4d", *(A + r*nc + c));

  

        printf("\n");

    }

  

    printf("\n\n");

}

  
// Неквадратная матричная транспонирование матрицы размера rxc и базового адреса A

void MatrixInplaceTranspose(int *A, int r, int c)

{

    int size = r*c - 1;

    int t; // содержит элемент для замены, в конечном итоге становится следующим элементом для перемещения

    int next; // расположение 't' для перемещения

    int cycleBegin; // держит начало цикла

    int i; // итератор

    bitset<HASH_SIZE> b; // хеш для пометки перемещенных элементов

  

    b.reset();

    b[0] = b[size] = 1;

    i = 1; // Обратите внимание, что A [0] и A [size-1] не будут двигаться

    while (i < size)

    {

        cycleBegin = i;

        t = A[i];

        do

        {

            // Матрица ввода [rxc]

            // Выходная матрица

            // i_new = (i * r)% (N-1)

            next = (i*r)%size;

            swap(A[next], t);

            b[i] = 1;

            i = next;

        }

        while (i != cycleBegin);

  

        // Get Next Move (как насчет запроса случайного местоположения?)

        for (i = 1; i < size && b[i]; i++)

            ;

        cout << endl;

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main(void)

{

    int r = 5, c = 6;

    int size = r*c;

    int *A = new int[size];

  

    for(int i = 0; i < size; i++)

        A[i] = i+1;

  

    Print2DArray(A, r, c);

    MatrixInplaceTranspose(A, r, c);

    Print2DArray(A, c, r);

  

    delete[] A;

  

    return 0;

}

Выход:

   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

   1   7  13  19  25
   2   8  14  20  26
   3   9  15  21  27
   4  10  16  22  28
   5  11  17  23  29
   6  12  18  24  30

Продление: 17 марта 2013 г. Некоторые читатели выявили сходство между транспонированием матрицы и преобразованием строки . Без особой теории я представляю проблему и решение. В данном массиве таких элементов, как [a1b2c3d4e5f6g7h8i9j1k2l3m4]. Преобразуйте его в [abcdefghijklm1234567891234]. Программа должна работать на месте. Что нам нужно, так это транспонирование на месте. Ниже приведен код.

#include <stdio.h>
#include <iostream>
#include <bitset>
#define HASH_SIZE 128

  

using namespace std;

  

typedef char data_t;

  

void Print2DArray(char A[], int nr, int nc) {

   int size = nr*nc;

   for(int i = 0; i < size; i++)

      printf("%4c", *(A + i));

  

   printf("\n");

}

  

void MatrixTransposeInplaceArrangement(data_t A[], int r, int c) {

   int size = r*c - 1;

   data_t t; // содержит элемент для замены, в конечном итоге становится следующим элементом для перемещения

   int next; // расположение 't' для перемещения

   int cycleBegin; // держит начало цикла

   int i; // итератор

   bitset<HASH_SIZE> b; // хеш для пометки перемещенных элементов

  

   b.reset();

   b[0] = b[size] = 1;

   i = 1; // Обратите внимание, что A [0] и A [size-1] не будут двигаться

   while( i < size ) {

      cycleBegin = i;

      t = A[i];

      do {

         // Матрица ввода [rxc]

         // Выходная матрица

         // i_new = (i * r)% size

         next = (i*r)%size;

         swap(A[next], t);

         b[i] = 1;

         i = next;

      } while( i != cycleBegin );

  

      // Get Next Move (как насчет запроса случайного местоположения?)

      for(i = 1; i < size && b[i]; i++)

         ;

      cout << endl;

   }

}

  

void Fill(data_t buf[], int size) {

   // Заполнить abcd ...

   for(int i = 0; i < size; i++)

   buf[i] = 'a'+i;

  

   // Заполнить 0123 ...

   buf += size;

   for(int i = 0; i < size; i++)

      buf[i] = '0'+i;

}

  

void TestCase_01(void) {

   int r = 2, c = 10;

   int size = r*c;

   data_t *A = new data_t[size];

  

   Fill(A, c);

  

   Print2DArray(A, r, c), cout << endl;

   MatrixTransposeInplaceArrangement(A, r, c);

   Print2DArray(A, c, r), cout << endl;

  

   delete[] A;

}

  

int main() {

   TestCase_01();

  

   return 0;

}

++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++

Рекомендуемые посты:

Inplace (фиксированное пространство) M x N размер матрицы транспонировать | обновленный

0.00 (0%) 0 votes