matrixInplaceTranspose.scala

// quick translation from http://www.geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/

def matrixInplaceTranspose[A](a: Array[A], rows: Int, columns: Int): Unit = {
  val size = rows * columns - 1
  // bitset<HASH_SIZE> b; // hash to mark moved elements
  val b = new collection.mutable.BitSet(size)
  b.add(0)
  b.add(size)
  var i = 1; // Note that A[0] and A[size-1] won't move
  while (i < size) {
    val cycleBegin = i
    var t = a(i)
    do {
      // Input matrix [r x c]
      // Output matrix 1
      // i_new = (i*r)%(N-1)
      val next = (i * rows) % size
      val t1 = a(next)
      a(next) = t
      t = t1
      b.add(i)
      i = next
    }
    while (i != cycleBegin)
 
    // Get Next Move (what about querying random location?)
    i = 1
    while (i < size && b.contains(i)) i += 1
  }
}

val x = Vector(
    Vector("a1", "a2", "a3", "a4", "a5", "a6"), Vector("b1", "b2", "b3", "b4", "b5", "b6"), Vector("c1", "c2", "c3", "c4", "c5", "c6")
  )

val z = x.map(_.toArray).toArray
val z1 = z.flatten
matrixInplaceTranspose(z1, z.length, z(0).length)
val y = x.transpose // inefficient
assert(y.flatten sameElements z1)
matrixInplaceTranspose(z1, z(0).length, z.length)
assert(x.flatten sameElements z1)