transpose 1D array of leading dimension N

Question

how can i transpose an 1d array of leading dimension N, without extra space ? any language is fine

Answer 1

Simplest approach is just:

for each m
  for each n
    if m != n 
       swap A[m][n] and A[n][m]

This only works for square matrices of course. For in-place transpose of rectangular matrices things get a little trickier.

Answer 2

Transposing a non-square matrix in-place represented as a linear array is a bit of a trick.

Here is a REXX program that performs an in-place transpose of a 2D matrix represented in a one dimensional array of size M * N where M is the number of rows and N is the of columns in the non-transposed array. Once transposed, M becomes the number of columns and N becomes the number of rows.

i = 0                /* linear array index */ 
do j = 1 to N        /* j = 1 to columns of non-transposed array */ 
  do k = 1 to M      /* k = 1 to rows of non-transposed array */ 
    i = i + 1
    t = (k - 1) * N + j 
    do while t < i 
      jp = (t - 1) % M + 1 
      kp = t - (jp - 1) * M 
      t = (kp - 1) * N + jp 
    end 
    if i \= t then say 'exchange('i',' t')'   /* swap elements */
  end 
end

The above program displays array elements that must be exchanged to yield a transposed array.

This program will work for any sized matrix represented as a linear array where the elements are arranged by column then row. For example, an M by N matrix will have its elements arranged as follows:

X_1,1, X_1,2, ... X_1,N, X_2,1, X_2,2, ... X_2,N, ... X_M,N

The program prints out the linear array indices of the elements that need to be exchanged to yield a transposed matrix of the form:

X_1,1, X_2,1, ... X_M,1, X_1,2, X_2,2, ... X_M,2, ... X_M,N

For example, start with M = 4, N = 2 and an array containing:

A1, B1, A2, B2, A3, B3, A4, B4

Perform the following exchanges:

exchange(2, 3) 
exchange(3, 5) 
exchange(4, 7) 
exchange(6, 7)

and the arrangement becomes:

A1, A2, A3, A4, B1, B2, B3, B4

How does this work?

Start with a notation to identify each element in the linear array as:

X[i,j,k] 

where: i is the linear array index for an element in X 
       j is the row number for element in X
       k is the column number for element in X

Using this notation, an array in row major order can be generated as:

i = 0 
do j = 1 to M    /* Row counter */ 
  do k = 1 to N  /* Column counter */ 
    i = i + 1     /* array index of element j, k */ 
    say 'X['i','j','k']' 
  end 
end

Note that given values for j (row) and k (column), i, the linear array index for X_i,j, may be calculated as:

i = (j - 1) * N + k 

The transpose of matrix X is constructed by exchanging elements X[i,j,k] with X[t,k,j] over the range of j = 1 to M and k = 1 to N provided i > t. In essence we exchange all row variables for column variables. Using the notation described above, this amounts to exchanging linear array elements:

exchange(X[i,j,k], X[t,k,j])

Given values for j and k we can calculate the values of i and t as:

   i = (j - 1) * N + k
   t = (k - 1) * M + i

Now, proceed through the linear array making the above exchanges as i is increased from 1 to M * N. Notice that after each iteration all elements of X having an index less than or equal to i have been transposed. This is because each iteration only completes when the correct element has been exchanged into X[i].

Whenever i > t, it means that a prior exchange took place at index t. The element at t was exchanged as indicated above placing it at some new position t^prime. Given an index t, we may calculate the row major index t^prime as well as the row and column numbers associated with it as follows:

j^prime = (t - 1) % M + 1
k^prime = t - (j^prime - 1) * M
t^prime = (k^prime - 1) * N + j^prime

Again, if t^prime is less than i, it means that this element was exchanged too and we must continue with another round of calculations. Set t to the calculated t^prime and repeat. Eventually, i will become less than t and the exchange may be done. Basically we follow the element through all of its prior exchanges until we find it at i or to the right of i in the linear array.

Repeat this cycle for each element in the linear array and the matrix will have been transposed.