Take N elements from List of Lists

Question

I've come with a solution super tricky for a simple requirement. I think I could solve the problem using LinQ, but I'm not seeing it so clearly at all. What's sure, I'm not comfortable with my code.

The requirement is the following:

Given a list of lists of string (IEnumerable>), take the first N elements from each but one by one. So given this list of list and N=10:

{aaa, bb, ccc, ddd}
{eee, fff}
{ggg, hhhhh, iii, jjj, kkk}
{lll}
{1111, 22, 333, 444, 55555, 66666}

This is the output:

{aaa, eee, ggg, lll, 111, bb, fff, hhhhh, 22, ccc}

And here is the code:

private IEnumerable<string> Extract(
    IEnumerable<IEnumerable<string>> listOfList,
    int N
)
{
    var result = new List<string>();

    for (int i = 0; i < N; i++)
    {
        foreach (IEnumerable<string> list in listOfList)
        {
            if (list.Count() > i)
            {
                result.Add(list.ElementAt(i));

                if (result.Count >= N)
                    return result;
            }
        }
    }

    return result;
}

The code works, but I don't think this is maintainable nor easy to read. Thanks.

Answer 1

Calling ElementAt() inside a loop will cause the IEnumerable to be called multiple times. This code isn't deferring execution either.

Now if you think the previous code wasn't readable then hold on to your hats. I'm going to post some code in hopes someone can build on it and maybe come up with something better.

public static class IEnumerableExtensions
{
    public static IEnumerable<TSource> Interweave<TSource>(this IEnumerable<TSource> source, params IEnumerable<TSource>[] weavers)
    {
        // Create a list of Enumerators but need to reverse it as will be removing from list and don't want o mess up indexer
        var enumerators = new[] { source }.Concat(weavers).Select(x => x.GetEnumerator()).Reverse().ToList();
        try
        {
            while (enumerators.Count > 0)
            {
                //  index backwards so we can remove from list and not mess up index
                for (var i = enumerators.Count - 1; i >= 0; i--)
                {
                    var currentEnumerator = enumerators[i];
                    if (currentEnumerator.MoveNext())
                    {
                        yield return currentEnumerator.Current;
                    }
                    else
                    {
                        currentEnumerator.Dispose();
                        enumerators.Remove(currentEnumerator);
                    }
                }
            }
        }
        finally
        {
            // finally block as we can't use "using" as have multiple disposables and don't know count ahead of time
            if (enumerators != null)
            {
                enumerators.ForEach(x => x.Dispose());
            }
        }
    }
}

This doesn't do Take, but you can just chain on the Take method.

Example of it in use:

static void Main(string[] args)
{
    var one = new[] { "aaa", "bb", "ccc", "ddd" };
    var two = new[] { "eee", "fff" };
    var threee = new[] { "ggg", "hhhhh", "iii", "jjj", "kkk" };
    var four = new[] { "lll" };
    var five = new[] { "1111", "22", "333", "444", "55555", "66666" };

    foreach (var item in one.Interweave(two, threee, four, five).Take(6))
    {
        Console.WriteLine(item);
    }
    Console.ReadLine();
}

Answer 2

A few comments about the API which completely ignore the spec:

• I would rename N to count, which is descriptive and follows typical naming conventions. Your method would benefit from inline documentation (///), which could clarify the behaviour (what does Extract mean?!?) and describe the parameters precisely.

• It's good that you've used the general-purpose IEnumerable as the return type (gives you freedom to use lazy implementations like those provided by the other answers). I would consider removing the count parameter: the consumer can use LINQ's Take if they want. Currently the API means you can't just keep consuming stuff until you get bored (e.g. with TakeWhile or something), and lacks a specification as to what the method should do if it runs out of stuff to return, what to do with invalid inputs (e.g. -1) ,and all that fun stuff that comes with providing a nontrivial API.

• Note that t3chb0t has provided a generic implementation, so it works with lists of anything, and not just strings. There is basically no reason not to do this, and it means you will have a nice reusable piece of code that works with any type.

• Again, t3chb0t has made the method a static extension method: there is no need for your method to be an instance method unless it is swappable behaviour, which is not implied by the spec. An extension method means it will fit in nicely with the other LINQ methods that most of us use daily.

Answer 3

CharlesNRice's solution has still one flaw. It eagerly enumerates the main collection and since we don't know its length, we better avoid it. Since the other answer already mentions flaws in your code, let me just add this lazy alternative.

---

It's a little bit tricky to make it deferred because you first need to enumerate the main collection and create enumerators for each sub-collection, this is what I use the isQueuePopulated flag for. Then you need to collect them in the queue for as long as you're enumerating the main collection. When this is done, you need to switch to the queue, then you Dequeue the first enumerator, try to MoveNext and if it succeeded, you return Current and Enqueue the enumerator for later.

public static IEnumerable<T> TakeEach<T>(this IEnumerable<IEnumerable<T>> source, int count)
{
    var counter = 0;
    var queue = new Queue<IEnumerator<T>>();
    var mainEnumerator = source.GetEnumerator();
    var isQueuePopulated = false;
    try
    {
        var e = default(IEnumerator<T>);
        while (!isQueuePopulated || queue.Any())
        {
            if (!isQueuePopulated && mainEnumerator.MoveNext())
            {
                e = mainEnumerator.Current.GetEnumerator();
            }
            else
            {
                isQueuePopulated = true;
            }

            e = isQueuePopulated ? queue.Dequeue() : e;

            if (e.MoveNext())
            {
                queue.Enqueue(e);
                yield return e.Current;

                if (++counter == count)
                {
                    yield break;
                }
            }
            else
            {
                e.Dispose();
            }
        }
    }
    finally
    {
        mainEnumerator.Dispose();
        foreach (var e in queue)
        {
            e.Dispose();
        }

    }
}

Answer 4

Another opportunity to solve this problem is to use Transpose() in MoreLinq with Linq itself:

var listoflists = new List<List<string>>() { one, two, three, four, five };
var res = listoflists.Transpose()
    .SelectMany(x => x)
    .Take(10);

Result: { "aaa", "eee", "ggg", "lll", "1111", "bb", "fff", "hhhhh", "22", "ccc" }

Answer 5

Here is another generic and deferred extension method version that seems to work for me. We iterate through all sequences one by one at once and only stop when there is nowhere to go within any sequence or the number of items requested have already been yielded.

    public static IEnumerable<TIn> FecthFromEach<TIn>(
        this IEnumerable<IEnumerable<TIn>> sequences,
        int maxLimit)
    {
        var enumerators = sequences.Select(_ => _.GetEnumerator()).ToList();
        var length = enumerators.Count;
        var breakEnumerators = new bool[length];            
        var count = 0;

        try
        {
            while (count < maxLimit && breakEnumerators.Any(_ => !_))
            {
                foreach (var i in Enumerable.Range(0, length))
                {
                    if (count >= maxLimit) break;

                    if (!enumerators[i].MoveNext()) breakEnumerators[i] = true;
                    else
                    {
                        yield return enumerators[i].Current;
                        ++count;
                    }
                }
            }                
        }
        finally
        {
            enumerators.ForEach(_ => _.Dispose());
        }
    }

Here are the test cases that I use to confirm it's working as expected:

[TestFixture]
public class CollectionExtentionsTests
{        
    [TestCaseSource(nameof(CountResultPairs))]
    public void TestFetchFromEach(Tuple<int, int[]> pair)
    {
        var l1 = new[] { 1, 11, 111, 1111, 11111 };
        var l2 = new[] { 2, 22 };
        var l3 = new[] { 3 };
        var l4 = new[] { 4, 44, 444, 4444 };
        var l5 = new[] { 5, 55, 555 };

        var input = new[] { l1, l2, l3, l4, l5 };

        var result = input.FecthFromEach(pair.Item1);

        CollectionAssert.AreEqual(pair.Item2, result);
    }

    private static IEnumerable<Tuple<int, int[]>> CountResultPairs
    {
        get
        {
            yield return Tuple.Create(10, new[] { 1, 2, 3, 4, 5, 11, 22, 44, 55, 111 });
            yield return Tuple.Create(11, new[] { 1, 2, 3, 4, 5, 11, 22, 44, 55, 111, 444 });
            yield return Tuple.Create(12, new[] { 1, 2, 3, 4, 5, 11, 22, 44, 55, 111, 444, 555 });
            yield return Tuple.Create(13, new[] { 1, 2, 3, 4, 5, 11, 22, 44, 55, 111, 444, 555, 1111 });
            yield return Tuple.Create(14, new[] { 1, 2, 3, 4, 5, 11, 22, 44, 55, 111, 444, 555, 1111, 4444 });
            yield return Tuple.Create(15, new[] { 1, 2, 3, 4, 5, 11, 22, 44, 55, 111, 444, 555, 1111, 4444, 11111 });
            yield return Tuple.Create(115, new[] { 1, 2, 3, 4, 5, 11, 22, 44, 55, 111, 444, 555, 1111, 4444, 11111 });
        }
    }
}

Note that I used int instead of string in the tests but it should affect anything anyway.