Merge Lists within List that share same property C#

Question

I have shapes of different colour.

Shape pink = new Shape() { name = "Pink" };
Shape yellow = new Shape() { name = "Yellow" };
Shape red = new Shape() { name = "Red" };
Shape white = new Shape() { name = "White" };
Shape blue = new Shape() { name = "Blue" };

Each shape returns a List of any other shapes it's touching, which is stored in a List.

List<List<Shape>> lists;

So lists could look like this

lists = new List<List<Shape>>()
{
    new List<Shape>() { pink, yellow },
    new List<Shape>() { yellow, pink, red },
    new List<Shape>() { red, yellow},
    new List<Shape>() { white, blue},
    new List<Shape>() { blue, white}
};

which I'd like to condense and have finish up as a new List of touching shape Lists.

List<List<Shape>> result

In this instance result contains just two

List<Shape>

for example

 {{pink, yellow, red}, { white, blue}}

Where the child lists share some common denominator.

I've not been able to get this working with loops, and I'm not that familiar with Linq.

Another scenario would be

lists = new List<List<Shape>>()
{
    new List<Shape>() { pink, yellow },
    new List<Shape>() { yellow, pink, red },
    new List<Shape>() { red, yellow, blue},
    new List<Shape>() { white, blue,},
    new List<Shape>() { blue, white, red}
};

And result List should only contain one List

{{pink, yellow, red, blue, white}}

because all previous Lists have some relative colours.

I couldn't understand the relation between the first list and the second one. — Oshi
– Oshi, Commented Mar 19, 2019 at 8:41
It is currently not totally clear, what the second list contains. What would happen for instance, if there would be the additional list with [blue, red]? — Malior
– Malior, Commented Mar 19, 2019 at 8:50

Malior · Accepted Answer · 2019-03-19 10:03:45Z

1

I tried it, also with using linq. Just replace the string with your shape. but the string makes it atm easier to get the idea of the algorithm. Please check the comments in code for the differnet steps:

         var lists = new List<List<string>>();
        lists.Add(new List<string> { "a", "b", "c" });
        lists.Add(new List<string> { "a", "c" });
        lists.Add(new List<string> { "d", "e" });
        lists.Add(new List<string> { "e", "d" });
        lists.Add(new List<string> { "e", "a" }); // from my comment

        var results = new List<List<string>>();

        foreach (var list in lists)
        {
            // That checks, if for this list, there is already a list, that contains all the items needed.
            if (results.Any(r => r.Count == r.Union(list).Count()))
            {
                continue;
            }

            // get the lists, that contains at least one item of the current "list".
            // This is important, as depending on the amount of elements, there have to be specific further steps.
            var listsWithItemsOfList = results.Where(r => list.Any(x => r.Contains(x)));

            // if not item, then you just have to add the whole content, as non of the colors exist.
            if (!listsWithItemsOfList.Any())
            {
                results.Add(new List<string>(list));
            }
            // if exactly, one, that add all the items, that were missing
            // (it might be, that nothing is added in case list.Except(l) is empty.
            else if(listsWithItemsOfList.Count() == 1)
            {
                var listWithOneItem = listsWithItemsOfList.Single();
                listWithOneItem.AddRange(list.Except(listWithOneItem));
            }
            else
            {
                // if multiple elements, it's getting complicated.
                // It means, that all needed items are currently spreaded over multiple lists, that have now to be merged.
                var newMergedList = listsWithItemsOfList.SelectMany(x => x).Distinct().ToList(); // merge all into one
                results.RemoveAll(x => listsWithItemsOfList.Contains(x)); // remove those lists from results
                results.Add(newMergedList); // just add one new list, containing all.
            }
        }

edited Mar 19, 2019 at 10:03

answered Mar 19, 2019 at 9:31

Malior

1,40111 silver badges18 bronze badges

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

3 Comments

user2403710 Over a year ago

Thanks so much Malior, this is working as expected. Though it's a hard for me to understand exactly what's going on ;)

Malior Over a year ago

glad, that it helps. I just updated the comments, and added some new. I suggest, that you carefully debug it a little bit, and watch what happens. For me also, Lists in Lists are alreadys hard to understand, so, no worry. If everything works fine, please mark as solution.

user2403710 Over a year ago

Thank you Malior! Spent so many hours trying to get this working :/ Each time I'd get close but been staring at it for so long I could not see the wood for the trees!

Robin Bennett · Accepted Answer · 2019-03-19 09:07:42Z

0

Here's my attempt, using a mix of linq and loops. (which IME means it's possible to do it entirely in linq, at the risk of making it harder to read)

I sort the input with the longest lists first, then see if there's an existing output that contains every item in the input - if not I add a new one.

        var yellow = 0;
        var pink = 1;
        var red = 2;
        var white = 3;
        var blue = 4;

        var input = new List<List<int>> {
            new List<int> { pink, yellow },
            new List<int> { yellow, pink, red},
            new List<int> { red, yellow},
            new List<int> { white, blue},
            new List<int> { blue, white}
            };

        var output = new List<List<int>>();

        // Start with the longest lists
        foreach (var item in input.OrderByDescending(x => x.Count))
        {
            // See if it will fit in an existing output value
            var itemIsEntirelyContainedByExistingOutput = false;
            foreach (var outputValue in output)
            {
                if (item.All(colour => outputValue.Contains(colour)))
                {
                    itemIsEntirelyContainedByExistingOutput = true;
                    break;
                }
            }

            // No, so add this to the list of outputs
            if (!itemIsEntirelyContainedByExistingOutput)
            {
                output.Add(item);
            }
        }

Here's an attempt to condense it into linq. At this point it's much harder to debug, although I hope it's still readable.

        // Start with the longest lists
        foreach (var item in input.OrderByDescending(x => x.Count))
        {
            // See if it will fit in an existing output value
            if (!output.Any(x => item.All(x.Contains)))
            {
                // No, so add this to the list of outputs
                output.Add(item);
            }
        }

edited Mar 19, 2019 at 9:07

answered Mar 19, 2019 at 8:59

Robin Bennett

3,2411 gold badge11 silver badges22 bronze badges

1 Comment

user2403710 Over a year ago

Thanks so much Robin. It's close and certainly far less code than what I had written. I'm finding it difficult to explain full scenario, but in the case where: new List<int> { pink, yellow }, new List<int> { yellow, pink, red}, new List<int> { red, yellow, blue}, new List<int> { white, blue}, new List<int> { blue, white, red} Output should contain only one List of all colours because all Lists have shared colours. Does that makes sense?

Robin Bennett · Accepted Answer · 2019-03-20 09:09:05Z

0

I think I understand the problem now. The input defines which colours are linked to which other colours, and the results are a list of linked colours.

        // Build a list of distinct colours
        var allColours = input.SelectMany(x => x.Select(y => y)).Distinct();

        foreach (var colour in allColours)
        {
            // Find all colours linked to this one
            var linkedColours = input.Where(x => x.Contains(colour)).SelectMany(x => x.Select(y => y)).Distinct().ToList();

            // See if any of these colours are already in the results
            var linkedResult = results.FirstOrDefault(x => x.Any(y => linkedColours.Contains(y)));
            if (linkedResult == null)
            {
                // Create a new result
                results.Add(linkedColours);
            }
            else
            {
                // Add missing colours to the result
                linkedResult.AddRange(linkedColours.Where(x => !linkedResult.Contains(x)));
            }
        }

edited Mar 20, 2019 at 9:09

answered Mar 19, 2019 at 10:45

Robin Bennett

3,2411 gold badge11 silver badges22 bronze badges

2 Comments

user2403710 Over a year ago

Thanks Robin. This is close to the thought process I had to complete the task, but for me the Linq isn't working as intended. That last scenario should end up as one list in result. But when I test your code I get three?

Robin Bennett Over a year ago

@user2403710 - I've changed the code to expand the results when two sets of links overlap. I hope it now does what you want.

Collectives™ on Stack Overflow

Merge Lists within List that share same property C#

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related