"Turning" an IEnumerable<IEnumerable<T>> 90 degrees

Question

What I'm looking for is a basic operation (Which I'm sure have a name I'm just unaware of atm). I have a matrix like:

{1,2,3}

{A,N,F}

{7,8,9}

which I'd like to mutate into

{1,A,7}

{2,N,8}

{3,F,9}

(The above are only identifiers for objects not real values. The actual objects are of the same type and unordered)

I'd prefer a declarative solution to it but speed is a factor. I'm going to have to turn quite a few tables (100k cells a min) and a slow version would be on the critical path.

However I'm still more interested in a readable solution. I'm looking for alternative solutions to the below. (By alternative I do not mean variations but a different approach)

var  arrays = rows.Select(row => row.ToArray());
var cellCount = arrays.First().Length;
for(var i = 0;i<cellCount;i++){
  yield return GetRow(i,arrays);
}

IEnumerable<T> GetRow(int i,IEnumerable<T[]> rows){
  foreach(var row in rows}{
     yield return row[i]; 
  }
}

Amongst two almost equally readable solutions I'd go for the faster but readability goes before speed

EDIT It will always be a square matrix

Beka

It's called the transpose (en.wikipedia.org/wiki/Transpose) – Yardstick

I don't think it can get any more readable than this! – Duffey

Is it only for square matrices, or also for non-square? – Divulgate

@Novox thx I knew there was something my my algebra I'd forgotten – Beka

A rotation over 90 degrees clockwise would in fact give {7,A,1} {8,N,2} {9,F,3}. – Kwon

@Kwon you are right and I'm sure it's still obvious what I actually need though the "turn 90 degree" is not accurate – Beka

Answer 1

I'm a little iffy about this implementation. It has side-effects local to the iterator but looks logically clean to me. This assumes each sequence is the same length but should work for any. You can think of it as a variable length Zip() method. It should perform better than the other linked LINQ solutions found in the other answers as it only uses the minimum operations needed to work. Probably even better without the use of LINQ. Might even be considered optimal.

public static IEnumerable<IEnumerable<T>> Transpose<T>(this IEnumerable<IEnumerable<T>> source)
{
    if (source == null) throw new ArgumentNullException("source");
    var enumerators = source.Select(x => x.GetEnumerator()).ToArray();
    try
    {
        while (enumerators.All(x => x.MoveNext()))
        {
            yield return enumerators.Select(x => x.Current).ToArray();
        }
    }
    finally
    {
        foreach (var enumerator in enumerators)
            enumerator.Dispose();
    }
}

Agouti

Seems clean to me. It will be executed eagerly as far as I can see. Not an issue in my case since I will always have to iterate all. The method implementation might be had to read though the call side will be easy. – Beka

@Rune: What is it about this that might be hard to read? It's a rather simple implementation IMHO. – Agouti

On a side note, the second call to ToArray() could probably be removed. So a plus if you have many sequences to zip up. – Agouti

enumerators.All(x => x.MoveNext()) does not really follow "least surprise" since the usual Linq statement is side effect free – Beka

You actually don't need any of the ToArray it'll work without and if you move everything except for the first line into a different method it's also lazily evaluating as most linq methods are. If you hadn't already gotten the points at least a +1 for remembering to Dispose :) – Beka

@Rune: On second thought, for a general implementation (which is what I was aiming for), it needs to stay. It might be possible to access the rows out-of-order which results in an enumeration in-order. However in your case, I take it you are going to access it sequentially so it might not be a problem for you. – Agouti

Oh man, I just found a very similar implementation of Transpose() on an unrelated question. It's eerie. – Agouti

For a general implementation, this needs a check that the outer IEnumerable is not empty. Otherwise, the while loop runs forever (enumerable.All() is true for empty) and it yields empty arrays indefinitely. – Aristotle

Answer 2

Take a look at this extension method found here.

/// <summary>
/// Swaps the rows and columns of a nested sequence.
/// </summary>
/// <typeparam name="T">The type of elements in the sequence.</typeparam>
/// <param name="source">The source sequence.</param>
/// <returns>A sequence whose rows and columns are swapped.</returns>
public static IEnumerable<IEnumerable<T>> Transpose<T>(
         this IEnumerable<IEnumerable<T>> source)
{
    return from row in source
           from col in row.Select(
               (x, i) => new KeyValuePair<int, T>(i, x))
           group col.Value by col.Key into c
           select c as IEnumerable<T>;
}

I'm not sure about performance but the code looks elegant.

Otoscope

Answer 3

Here's mine if anyone's interested. It performs in the same sort of manner as Jeff's, but seems to be slightly faster (assuming those ToArrays() are necessary). There's no visible loops or temporaries, and it's much more compact:

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    return source
        .Select(a => a.Select(b => Enumerable.Repeat(b, 1)))
        .Aggregate((a, b) => a.Zip(b, Enumerable.Concat));
}

If you need it to handle empty lists too, then it becomes this:

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    return source
        .Select(a => a.Select(b => Enumerable.Repeat(b, 1)))
        .DefaultIfEmpty(Enumerable.Empty<IEnumerable<T>>())
        .Aggregate((a, b) => a.Zip(b, Enumerable.Concat));
}

I noticed that the asker wrote that the matrix would always be square. This implementation (and jeffs) will evaluate an entire row at a time, but if we know that the matrix is square we can rewrite the zip function in a more suitable manner:

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    return source
        .Select(a => a.Select(b => Enumerable.Repeat(b, 1)))
        .DefaultIfEmpty(Enumerable.Empty<IEnumerable<T>>())
        .Aggregate(Zip);
}

public static IEnumerable<IEnumerable<T>> Zip<T>(
    IEnumerable<IEnumerable<T>> first, 
    IEnumerable<IEnumerable<T>> second)
{
    var firstEnum = first.GetEnumerator();
    var secondEnum = second.GetEnumerator();

    while (firstEnum.MoveNext())
        yield return ZipHelper(firstEnum.Current, secondEnum);
}

private static IEnumerable<T> ZipHelper<T>(
    IEnumerable<T> firstEnumValue, 
    IEnumerator<IEnumerable<T>> secondEnum)
{
    foreach (var item in firstEnumValue)
        yield return item;

    secondEnum.MoveNext();

    foreach (var item in secondEnum.Current)
        yield return item;
}

This way, each element won't be evaluated until it's returned.

Farriery

Answer 4

Your question seems to be implying that you want to modify the original matrix.

If that's the case, and if you are able to store the matrix as a IList<IList<T>> matrix, then this will work, however, only in the case of a square matrix.

for(int i = 0; i < matrix.Count; ++i)
{
    for(int j = 0; j < i; ++j)
    {
        T temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp
    }
}

Divulgate

That's a specific version of the approach in the question relying on Ilist<Ilist<T>>. I'm looking for a different approach relying on IEnumerable<IEnumerable<T>> – Beka

Answer 5

Well, what you are looking for here is a transformation T[][] -> T[][]. There are plenty of IEnumerabe<IEnumerable<T>>.Transpose() solutions around but they all boil down to looping enumerables using temporary lookups/keys and they leave a lot to be desired when it comes to performance on huge volume. Your example actually works faster (though you could loose the second foreach too).

First ask "do I need LINQ at all". You have not described what the purpose of the transposed matrix will be and if the speed is indeed your concern you might do well to just stay away from the LINQ/foreach and do it the old fashioned way (for inside for)

Brisco

No I do not need linq which is why I asked for a declarative solution as opposed to a linq solution :). There's room for improving readability with out hurting performance but blindsidedly improving the readability can impact our performance. It is on the critical path – Beka

Answer 6

Here is my enumerator based solution, that attempts to use for to gain speed over foreach / LINQ:

public static IEnumerable<IEnumerable<T>> Pivot<T>(this IEnumerable<IEnumerable<T>> src) {
    var enums = src.Select(ie => ie.GetEnumerator()).ToList();
    var initialMoveNext = Enumerable.Repeat(true, enums.Count).ToList();

    for (; ; ) {
        var moveNext = initialMoveNext.ToArray(); // initialize to all true
        var hasMore = false;

        for (int j1 = 0; j1 < enums.Count; ++j1)
            if (moveNext[j1]) {
                moveNext[j1] = enums[j1].MoveNext();
                hasMore = hasMore || moveNext[j1];
            }

        if (!hasMore)
            break;

        IEnumerable<T> subEnum() {
            for (int j1 = 0; j1 < enums.Count; ++j1) {
                if (moveNext[j1])
                    yield return enums[j1].Current;
            }
        }

        yield return subEnum();
    }
    
    for (int j1 = 0; j1 < enums.Count; ++j1)
        enums[j1].Dispose();
}

Kira