Skip to content

Instantly share code, notes, and snippets.

@harrytallbelt
Last active June 10, 2020 17:12
Show Gist options
  • Save harrytallbelt/ed364f70cda10877ddecc566f8cbf813 to your computer and use it in GitHub Desktop.
Save harrytallbelt/ed364f70cda10877ddecc566f8cbf813 to your computer and use it in GitHub Desktop.
M*N matrix transposition in place (O(1) memory) in JavaScript and Python.
// 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
}
}
}
}
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment