Блог

У меня есть фигуры разного цвета.

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

Каждая фигура возвращает список любых других фигур, к которым она прикасается, который сохраняется в списке.

 List<List<Shape>> lists;
  

Итак, списки могут выглядеть следующим образом

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

который я хотел бы сконденсировать и завершить как новый список списков касательных фигур.

 List<List<Shape>> result 
  

В этом случае результат содержит только два

 List<Shape>  
  

например

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

Где дочерние списки имеют некоторый общий знаменатель.

Я не смог заставить это работать с циклами, и я не настолько знаком с Linq.

Другим сценарием было бы

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

И список результатов должен содержать только один список

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

потому что все предыдущие списки имеют некоторые относительные цвета.

Я попробовал это, также используя linq. Просто замените строку вашей формой. но строка упрощает понимание алгоритма. Пожалуйста, проверьте комментарии в коде для различных шагов:

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

Вот моя попытка, использующая сочетание linq и циклов. (что IME означает, что это можно сделать полностью в linq, рискуя затруднить чтение)

Сначала я сортирую входные данные по самым длинным спискам, затем проверяю, есть ли существующий вывод, содержащий каждый элемент во входных данных — если нет, я добавляю новый.

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

Вот попытка сконденсировать его в linq. На данный момент это намного сложнее отлаживать, хотя я надеюсь, что это все еще читаемо.

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

Думаю, теперь я понимаю проблему. Входные данные определяют, какие цвета связаны с какими другими цветами, и результатом является список связанных цветов.

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