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.

• VisualMelon: Would you mind clarifying the spec a little? Are you meant to take the first N elements of each list, but taking the first of each, then the second of each, etc. or are you meant to take the first N of the sequences defined by taking the first, then the second, etc. Your code (and the example and all the answers) currently do the second, but the spec sounds like it wants the first.

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();
}

• Peter Taylor: You can avoid the fiddly stuff with the list indices by using a queue instead.
• VisualMelon: This code isn't just more efficient, it will handle infinite and non-resuable IEnumerables, which the OP's code won't. I like the lists personally (though not-so-much the reverse order, and it would probably be tidier with a Queue); you might consider using RemoteAt(i) rather than Remove(currentEnumerator) to avoid a linear scan. There is also no utility in the null check in the finally.
• CharlesNRice: @VisualMelon RemoveAt would be better. The null check was from docs.microsoft.com/en-us/dotnet/csharp/language-reference/… where they have code of what using boils down to. I was wondering about it as well but put it in based on their example.
• benj2240: I think this is a great approach. Here's a fiddle of what it might look like with Dequeue + maybe re-Enque in place of Remove or RemoveAt. dotnetfiddle.net/sOYUn4
• t3chb0t: @benj2240 the queue's constructor is eager and will enumerate the main collection entirely.

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" }

• t3chb0t: The Transpose extension is implemented virtually exactly as we did it here ;)
• HelloWorld: yep ;) As opportunity to not implement it by yourself
• t3chb0t: And I find their _() hillarious. This should have never been accepted LOL
• t3chb0t: Although, now I think my solution is better because it's deferred on every collection. Theirs is using Acquire which is eager and enumerates the main collection completely.
• VisualMelon: @t3chb0t it doesn't have much choice, since it yields columns at a time ;) (good point non-the-less) (I also don't like that transpose method's API... transpose ought to be reversible in my book)

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.

• Toby Speight: You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer.