Interleaving multiple (more than 2) irregular lists using LINQ

Question

Say I have the following data

IEnumerable<IEnumerable<int>> items = new IEnumerable<int>[] { 
    new int[] { 1, 2, 3, 4 },
    new int[] { 5, 6 },
    new int[] { 7, 8, 9 }
};

What would be the easiest way to return a flat list with the items interleaved so I'd get the result:

1, 5, 7, 2, 6, 8, 3, 9, 4

Note: The number of inner lists is not known at runtime.

Answer 1

What you're describing is essentially a Transpose Method where overhanging items are included and the result is flattened. Here's my attempt:

static IEnumerable<IEnumerable<T>> TransposeOverhanging<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    var enumerators = source.Select(e => e.GetEnumerator()).ToArray();
    try
    {
        T[] g;
        do
        {
            yield return g = enumerators
                .Where(e => e.MoveNext()).Select(e => e.Current).ToArray();
        }
        while (g.Any());
    }
    finally
    {
        Array.ForEach(enumerators, e => e.Dispose());
    }
}

Example:

var result = items.TransposeOverhanging().SelectMany(g => g).ToList();
// result == { 1, 5, 7, 2, 6, 8, 3, 9, 4 }

Answer 2

The solution below is very straight forward. As it turns out, it is also nearly twice as fast as the solution proposed by dtb.

private static IEnumerable<T> Interleave<T>(this IEnumerable<IEnumerable<T>> source )
{
    var queues = source.Select(x => new Queue<T>(x)).ToList();
    while (queues.Any(x => x.Any())) {
        foreach (var queue in queues.Where(x => x.Any())) {
            yield return queue.Dequeue();
        }
    }
}