M*N matrix transposition in place (O(1) memory) in JavaScript and Python.

transpose-in-place.js

// matrix -- a 1D array, that stores matrix A[rows,columns] by rows
// i.e. [A[0,0],A[0,1],..,A[0,columns-1],A[1,0],A[1,1],..,A[1,columns-1],..]
// rows -- number of rows in A
// columns -- number of columns in A
function transpose(matrix, rows, columns) {
  // Let's write down some index conversion functions.
  // You can convert 1D array index to
  // (rows*columns) matrix index like that
  const C = k => [Math.floor(k / columns), k % columns]
  // You can do the reverse this way:
  const C_rev = ([i, j]) => i*columns + j
  // If you want to treat your 1D array as
  // a transposed (columns*rows) matrix instead,
  // you can do so with this conversion:
  const C_trans = k => [Math.floor(k / rows), k % rows]
  // To transpose 2D indexes you simply do that:
  const T = ([i, j]) => [j, i]
  // Now we can write down this function:
  // given 1D index k, return the current 1D index of the element
  // that should be stored at k after transposition
  const transposedIndex = k => C_rev(T(C_trans(k)))
  // You can totaly get rid of C, C_rev, C_trans, and T, and simplify
  // the last function to k => (k % rows) * columns + Math.floor(k / rows)
  // It's written like that for clarity's sake.

  // This function can be iterated like that:
  // k_0 = ... some valid 1D array index ...
  // k_n+1 = transposedIndex(k_n)
  // Because the function's domain and codomain
  // are the same *finite* set {0,1,...,rows*columns-1},
  // the iteration would necessarily produce a cycle.

  // It is not necessary, however, that there would
  // only be one cycle. In fact, there would be at least three,
  // because 0 and rows*columns-1 are function's fixed points.

  // After isolating all the unique cycles and swapping (* see below)
  // the values of the array according to them, we will have our matrix
  // transposed. It follows from the definition of transposedIndex function:
  // after the swapping, at each index k the array will hold
  // "the element, that should be stored at k after transposition".

  // (*) "swapping" the array's values according to the cycle G of length N,
  // is equivalent to doing this assignments in parallel:
  //   matrix[G(1)] = matrix[G(2)]
  //   matrix[G(2)] = matrix[G(3)]
  //     . . .
  //   matrix[G(N-1)] = matrix[G(N)]
  //   matrix[G(N)]   = matrix[G(1)]

  // Let's iterate through all the array indexes
  // to make sure we've found every cycle.
  for (let i = 0; i < rows * columns; ++i) {
    // As we remember, each array index will produce a cycle,
    // according to which the elements should be swapped -- a swap-cycle.
    // The same swap-cycle of length N, will be produced by
    // N different indexes of the array (the ones that are in the cycle).
    // We need to apply swapping according to each cycle once and only once,
    // so we need to check if the swap-cycle produced by i was applied before.
    // For that, we iterate through cycle and make sure that each of its
    // elements is >= i. If there is an element k, such that k < i,
    // that means that we would have applied this cycle on
    // a previous iteration: either when i was equal to k or
    // even earlier, if k isn't the smallest element of the cycle.
    let k = i
    let swapCycleAlreadyApplied = false
    do {
      k = transposedIndex(k)
      if (k < i) {
        swapCycleAlreadyApplied = true
        break
      }
    } while (k != i)
    // If we found a swap-cycle that wasn't applied before,
    // we apply it (see the comment marked with (*) above to see
    // which array element goes where).
    // Similarly to doing a regular two-variable swap (which you could
    // think of as applying a swap-cycle of length 2), we will need
    // a temporary variable to store the first element of the cycle.
    if (!swapCycleAlreadyApplied) {
      const firstCycleValue = matrix[i]
      let curr = i
      let next = transposedIndex(i)
      while (next != i) {
        matrix[curr] = matrix[next]
        curr = next
        next = transposedIndex(next)
      }
      matrix[curr] = firstCycleValue
    }
  }
}


// Ok, so this can actually be improved a little bit.
// If you do several examples by hand, you
//   1) are apparently really commited to that thing for some reason;
//   2) will find out that the cycles are mirrored with respect to the
// middle element of the matrix. I.e., if you have a cycle G: G(1), ... , G(m),
// then you will also have a cycle G': G'(1),  ... , G'(m),
// such that G'(k) == matrix.length - G(k).
// Except, sometimes it is not true. Sometimes the two mirrored cycles actually
// merge into one. This happens when one of the cycles (well, the other one
// mirrors it, so both, really) jumps to an element of the mirrored cycle.
// In terms of transposedIndex function, all this means that the transposedIndex
// of the "reflection" of an index k (i.e. (n-1)-k) is simply
// the "reflection" of transposedIndex(k):
//   transposedIndex((n-1)-k) == (n-1) - transposedIndex(k), for 0 <= k < n.
// The formal proof of this property is left for the reader as an exercise,
// because I simply couldn't do that myself. But you can convince yourself
// that this must be true by running this function on several matrix sizes:
  // function check(rows, columns) {
  //   const n = rows * columns
  //   const transposedIndex = k =>
  //     (k % rows) * columns + Math.floor(k / rows)
  //   const indexes = Array(n).fill().map((_, i) => i)  // [0,1,...,n-1]
  //   return indexes.every(k =>
  //     transposedIndex((n-1)-k) == (n-1) - transposedIndex(k))
  // }
// So, in conclusion, we can do half as many iterations (and check half as many
// cycles), if we take This mirroring property into account.
// We do have to check whether the cycle actually has a mirrored cycle
// or are they merged into one, though. If they did, the resulting cycle still
// has two halves that are mirrored, but at the end insted of "closing" them
// into separate cycles, we'll have to "glue" them together
// (it's easier to understand once you've seen the code).

// The function is the same as before, except for the commented lines.
function transposeOptimised(matrix, rows, columns) {
  const n = rows*columns
  const transposedIndex = k =>
    (k % rows) * columns + Math.floor(k / rows)

  // We only iterate through the first half of the matrix indexes,
  // all the other ones get checked for free because of the symmetry.
  for (let i = 0; i < Math.floor(n/2); ++i) {
    let k = i
    let swapCycleAlreadyApplied = false
    do {
      k = transposedIndex(k)
      if (k < i || k > (n-1-i)) {
        swapCycleAlreadyApplied = true
        break
      }
    } while (k != i)
    if (!swapCycleAlreadyApplied) {
      // Here we apply either both swap cycles simultaneously
      // or, if the cycles are merged in one, we start from two different
      // mirrored positions, apply the two mirrored halves of the cycle
      // simultaneously, and then "glue" them together.
      // Les't remind ourselves that "mirror reflection" of k is (n-1)-k and
      // transposedIndex of reflection of k is reflection of transposedIndex(k):
      // transposedIndex((n-1)-k) is (n-1)-transposedIndex(k).
      const firstCycleValue = matrix[i]
      const firstMirrorCycleValue = matrix[n-1-i]
      let curr = i
      let next = transposedIndex(i)
      // Exit either when the original cycle has come to its end (next == i)
      // or when it has merged whith the mirrored cycle (next == (n-1)-i).
      while (next != i && next != (n-1-i)) {
        matrix[curr] = matrix[next]
        matrix[n-1-curr] = matrix[n-1-next]
        curr = next
        next = transposedIndex(next)
      }
      if (next == i) {
        // If we had two cycles, we close them with these assignments.
        matrix[curr] = firstCycleValue
        matrix[n-1-curr] = firstMirrorCycleValue
      } else {
        // If, on the other hand, we had one large cycle, it means we
        // loopped through two its halves and now we "glue" them together.
        // We know that next == (n-1)-i. Value for this index is stored
        // at firstMirrorCycleValue. Also, next == (n-1)-i ==> (n-1)-next == i,
        // so (n-1)-curr should be assinged with the value at i,
        // which stored at firstCycleValue. So the assignments are the other
        // way around.
        matrix[curr] = firstMirrorCycleValue
        matrix[n-1-curr] = firstCycleValue
      }
    }
  }
}

transpose.py

def transpose(matrix, rows, columns):
    n = rows * columns
    transposed_index = lambda k: (k % rows) * columns + (k // rows)

    for i in range(n // 2):
        k = i
        swap_cycle_already_applied = False
        while True:
            k = transposed_index(k)
            if not i <= k <= (n-1)-i:
                swap_cycle_already_applied = True
                break
            if k == i:
                break
        if not swap_cycle_already_applied:
            first_cycle_value = matrix[i]
            first_mirror_cycle_value = matrix[(n-1)-i]
            curr = i
            next = transposed_index(i)
            while next != i and next != (n-1)-i:
                matrix[curr] = matrix[next]
                matrix[(n-1)-curr] = matrix[(n-1)-next]
                curr = next
                next = transposed_index(next)
            if next == i:
                matrix[curr] = first_cycle_value
                matrix[(n-1)-curr] = first_mirror_cycle_value
            else:
                matrix[curr] = first_mirror_cycle_value
                matrix[(n-1)-curr] = first_cycle_value