Merging multiple lists

Question

Given that there I have a list of lists, List<List<T>>, in which all lists contain 0 or more items, likely, but not necessarily all the same number. And I would like tho have a list containing all the items in the Lists... but I want the order to be as follows: first the first items off all the lists, in order that they appear in the 'super-list'.

Ex.

List[0] = { 'Apple', 'Blueberry', 'Cranberry' }
List[1] = { 'Anteater', 'Baboon', 'Camel', 'Dodo'}
List[2] = { 'Albatross', 'Blackbird', 'Chicken'}

result = { 'Apple', 'Anteater', 'Albatross', 'Blueberry', 'Baboon', 
           'Blackbird', 'Cranberry', 'Camel', 'Chicken', 'Dodo' }

(note that this is NOT alphabetical order, Blueberry comes before Baboon)

Ofcourse, i could just loop through the 'superlist' with a counter, adding items to the resultslist one by one, as long as there is a list that isn't empty:

int i = 0;
bool done = false;

while (!done)
{
    bool found = false;

    foreach (list l in superlist)
    {
        if (l.Count() > i)
        {
           found = true;
           result.Add(l[i]);
        }
    }

    i++;

    if (!found)
        done = true;
}

But it would be way nicer to use some optimized LINQ function to do this. I have been looking into Zip, GroupBy and Aggregate, but couldn't get them to work.

So: Is there a pretty LINQ function, or combination of multiple, that would turn this into pretty code, or should I stick by (and maybe optimize) my current function?

Edit: A simple SelectMany(x => x) also doesn't do the trick, as it preserves the order of the lists, instead of folding them, like my algorithm does. See my initial question for more details.

Duplication of this: stackoverflow.com/questions/1590723/flatten-list-in-linq — ataravati
– ataravati, Commented Aug 23, 2013 at 19:00

I4V · Accepted Answer · 2013-08-23 19:12:33Z

8

You need SelectMany

var result = lists.SelectMany(x => x.Select((s, inx) => new { s, inx }))
                .GroupBy(x => x.inx)
                .SelectMany(x => x.Select(y => y.s))
                .ToList();

EDIT

For those, who want to try, the initialization code.

List<List<string>> lists = new List<List<string>>()
        {
            new List<string>(){ "Apple", "Blueberry", "Cranberry" },
            new List<string>(){ "Anteater", "Baboon", "Camel", "Dodo"},
            new List<string>(){ "Albatross", "Blackbird", "Chicken"},
        };

EDIT 2

OUTPUT: Apple,Anteater,Albatross,Blueberry,Baboon,Blackbird,Cranberry,Camel,Chicken,Dodo

edited Aug 23, 2013 at 19:12

answered Aug 23, 2013 at 18:47

I4V

35.4k6 gold badges71 silver badges82 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Amy Over a year ago

Totally works! Never would have come up with that, now as to the question whether this is more readable code? I'll leave that as an exercise to the reader.

King King Over a year ago

@Amy this works in any case (even with duplicated items in lists, ...) but if your list doesn't have duplicated items, my code also works.

King King Over a year ago

@I4V what is a1,a2,a3? We are talking about List<List<string>>?

I4V Over a year ago

@KingKing No worries, I removed my comment.

Kirk Broadhurst Over a year ago

@I4V I did - no notification on an edit. But I've now swapped by downvote for an upvote ;)

|

evanmcdonnal · Accepted Answer · 2013-08-23 18:56:16Z

1

Just use MyListOfLists.SelectMany(x => x).OrderByDescending(x => x).ToList()

SelectMany will flatten your lists into one. OrderByDescending operates on that result and will put the results in alphabetical order (which I think you want). Then call ToList to force execution and get a List<string> instead of an IEnumerable<string>

edited Aug 23, 2013 at 18:56

answered Aug 23, 2013 at 18:48

evanmcdonnal

48.5k17 gold badges111 silver badges119 bronze badges

Comments

Ivan Stoev · Accepted Answer · 2015-10-20 10:16:56Z

I know I'm late to the party, but since this post has been referenced from another post I was working on as a base for solving the problem, I feel it's necessary to add something to the subject.

There are two conflicting statements in the question:

But it would be way nicer to use some optimized LINQ function to do this.

and then

So: Is there a pretty LINQ function, or combination of multiple, that would turn this into pretty code, or should I stick by (and maybe optimize) my current function?

There is a big difference between optimized and pretty. Of course it depends of what does "optimized" mean. Pretty, readable, shorter code might be considered optimized for maintenance, but most of the time not for performance. So let speak about performance. The accepted answer might look cool, but is inefficient from both time and space (due to group by), and does not even provide the deferred execution behavior like the similar "standard LINQ" Concat function.

In that respect, the original function pprovided by the OP is much better. But we can go further and create a more generic function (not requiring lists) which does all this effectively and at the same time following the LINQ implementation spirit:

static class Extensions
{
    public static IEnumerable<T> Merge<T>(this IEnumerable<IEnumerable<T>> source)
    {
        var queue = new Queue<IEnumerator<T>>();
        IEnumerator<T> itemEnumerator = null;
        try
        {
            // First pass: yield the first element (if any) and schedule the next (if any)
            foreach (var list in source)
            {
                itemEnumerator = list.GetEnumerator();
                if (!itemEnumerator.MoveNext())
                    itemEnumerator.Dispose();
                else
                {
                    yield return itemEnumerator.Current;
                    if (itemEnumerator.MoveNext())
                        queue.Enqueue(itemEnumerator);
                    else
                        itemEnumerator.Dispose();
                }
            }
            // Second pass: yield the current element and schedule the next (if any)
            while (queue.Count > 0)
            {
                itemEnumerator = queue.Dequeue();
                yield return itemEnumerator.Current;
                if (itemEnumerator.MoveNext())
                    queue.Enqueue(itemEnumerator);
                else
                    itemEnumerator.Dispose();
            }
        }
        finally
        {
            if (itemEnumerator != null) itemEnumerator.Dispose();
            while (queue.Count > 0) queue.Dequeue().Dispose();
        }
    }
}

Note that I've could easily make it shorter by eliminating the repetitive parts and merging the two passes, but that would make it less readable and not faster (in fact it would be a little bit slower due to some additional checks needed).

To conclude: Library (reusable) code does not have to be (and is not in the most cases) cool or short. If it can, fine, but that should not be the driver.

user2711965 · Accepted Answer · 2013-08-23 18:48:30Z

0

Use Enumerable.SelectMany to flatten the items in the list and create a new list out of it.

var result = superlist.SelectMany(r=> r).ToList();

answered Aug 23, 2013 at 18:48

user2711965

1,8252 gold badges15 silver badges34 bronze badges

1 Comment

Kirk Broadhurst Over a year ago

This will not result in the required order.

King King · Accepted Answer · 2013-08-23 19:07:01Z

0

This works if the lists contains different items and there are not duplicated Items in a list.

var result = list.SelectMany(x=>x)
                 .OrderBy(x=>list.First(a=>a.Contains(x))
                                 .IndexOf(x));

edited Aug 23, 2013 at 19:07

answered Aug 23, 2013 at 18:59

King King

63.5k16 gold badges118 silver badges140 bronze badges

2 Comments

King King Over a year ago

@Amy a ha? I've tested it, as stated clearly if the requirement is OK, it outputs OK (with correct order).

King King Over a year ago

@Amy the list in my code is of type List<List<string>>, not a List<string>

2 revs · Accepted Answer · 2013-08-23 19:08:24Z

0

There is no easy or optimal (by the means of performance and code readability) way how to select the first element from all the lists, then the second, etc. with built-in linq extensions. However you could build your own extension from your code or if you don't like while loops as shown below:

public static class MyLinqExtensions
{
    public static void MySelect<T>(this IEnumerable<IEnumerable<T>> superlist)
    {
        int index = 0;

        foreach (IEnumerable<T> list in superlist)
        {
            if (index < list.Count())
            {
                yield return list.ElementAt(index);
            }

            index++;
        }
    }
}

Finally you can call Enumerable.Distinct() over the result to get unique values.

edited Aug 23, 2013 at 19:08

community wiki

2 revs
Jozef Benikovský

Comments

It'sNotALie. · Accepted Answer · 2013-08-23 19:18:22Z

0

I see what you're trying to do:

var result = input.SelectMany(l => l.Select((o, i) => new { o, i })).GroupBy(o => o.i).OrderBy(g => g.Key).SelectMany(g => g.Select(o => o.o);

edited Aug 23, 2013 at 19:18

answered Aug 23, 2013 at 19:10

It'sNotALie.

22.9k12 gold badges75 silver badges109 bronze badges

Collectives™ on Stack Overflow

Merging multiple lists

7 Answers 7

7 Comments

Comments

Comments

1 Comment

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

7 Comments

Comments

Comments

1 Comment

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related