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.

Answer 1

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

Answer 2

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

Answer 3

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