Matrix transpose algorithm

Question

If I have a List<List<T> like the following :

Name City Id
Anna NY 1
Joe NJ 2

How can I transpose it efficiently in order to have :

Name Anna Joe
City NY NJ
Id 1 2

I tried the following

public static void MatrixTranspose<T>(ref List<List<T>> matrix)
{ 
 var h = matrix.Count - 2;
 var w = matrix[0].Count - 1;
 for (var i = 0; i < h; ++i)
 {
 for (var j = i + 1; j < w; ++j)
 {
 var tmp = matrix[i][j];
 matrix[i][j] = matrix[j][i];
 matrix[j][i] = tmp;
 }
 }
}

That seems to be working on paper I believe? But I feel like I'm doing too much permutations. Is there a way to optimize it? Also, is the use of ref correct here?

• t3chb0t: That seems to be working on paper i believe? so you didn't actually test the code?
• Adriano Repetti: Few notes: is your matrix always square? If not then you have a bug. Is it List<List<T>> the proper type to use? Do you have the option to change it? ref has no use here because you never reassign its value to a new list. Performance? Worst case, probably, but it's probably also the easier to read. Do you have a measured performance issue?
• Ythio Csi: @t3chb0t : I tried, didn't work apparently. As Adriano Repetti pointed out, i'm out of range if i don't have a squared matrix.
• Ythio Csi: @AdrianoRepetti Matrix not always square, i saw the bug. List of List isn't necessarily the proper type to use, i can change it. In my context i just needed a place to store a collection of lists generated by the same loop. I transpose it because i need to foreach on the lines and serialize each line separatly later, so i want the lines to becomes the column for easier manipulations. Due to the version of .NET i'm using, i can't use Tuple and I can't use a Dictionnary because my keys would actually be a string, which is impossible.
• Adriano Repetti: Well, you might consider string[,] or even string[][]. Or you may let it be List<List<string>> but avoid to transpose the matrix. If it's only for visualization/serialization purposes then you just need to read values in the other order. Even better...create a View of underlying type and keep consumers unaware of its implementation/storage. Just few ideas to consider.

Answer 1

is the use of ref correct here?

Taken from MSDN: ref (C# Reference)

The ref keyword causes an argument to be passed by reference, not by value. The effect of passing by reference is that any change to the parameter in the called method is reflected in the calling method. For example, if the caller passes a local variable expression or an array element access expression, and the called method replaces the object to which the ref parameter refers, then the caller’s local variable or the array element now refer to the new object.

The point of ref is to pass a value type (struct) to a method as if it was reference type (class). List<T> is a class, so there's no need to add refin this scenario as it's just acting as another level of redirection. Think of it as being a pointer to a pointer.

The problem with using List<List<T> is that the size of the nested lists could differ from the top-level list and this wouldn't be a matrix. I'd recommend that you use something with a guaranteed rectangular structure, such as T[,]. i.e:

public static void MatrixTranspose<T>(ref T[,] matrix)
{
 int columns = matrix.GetLength(0);
 int rows = matrix.GetLength(1);
 T[,] transposed = new T[rows, columns];
 for (int row = 0; row < rows; row++)
 {
 for (int column = 0; column < columns; column++)
 {
 transposed[row, column] = matrix[column, row];
 }
 }
 // Reassign matrix so that it gets picked up by ref.
 matrix = transposed;
}