Как получить все возможные подсписки у списка? C#

Question

Подскажите, пожалуйста, есть ли встроенные функции или функции LINQ, которые позволяют получить все возможные комбинации элементов в списке? То есть, если у меня есть список {bread, milk, chips, mustard} получить комбинации

{(bread),(milk),(chips), (mustard), (bread milk), (bread chips), (bread mustard), (milk chips), (milk mustard), (chips mustard), (bread milk chips), (bread milk mustard), (bread chips mustard), (milk chips mustard), (bread milk chips mustard)}.

На вход функции подается одномерный список, а результатом будет двумерный. Если встроенных нет, есть какие-нибудь идеи, как это реализовать? Таких комбинаций будет

2^(количество элементов в списке) - 1.

У меня уже получалось реализовать 2-х элементные комбинации, но в данном случае, пока идей нет. Вот пример для 2-х элементных комбинаций:

                for (int i = 0; i < prevItemSet.Count - 1; i++)
            {
                for (int j = i + 1; j < prevItemSet.Count; j++)
                {
                    if (!ItemSetList[i].Equals(ItemSetList[j]))
                    {
                        bool isSub = false;
                        for (int l = 0; l < k - 1; l++)
                        {
                            if (ItemSetList[i][l] == ItemSetList[j][l])
                                isSub = true;
                            else
                            {
                                isSub = false;
                                break;
                            }
                                                              
                        }
                        if (isSub)
                        {
                            if (ItemSetList[i].Count == ItemSetList[j].Count)
                            {
                                var tempList = CombineItems(ItemSetList[i], ItemSetList[j]);
                                int supp = SupportCount(tempList);
                                if (!(tempList.Count == 0))
                                    nextCandidate.Add(tempList, supp);
                            }

                        }
                        //var tempList = CombineItems(ItemSetList[i], ItemSetList[j]);
                        //int supp = SupportCount(tempList);
                        //if (!(tempList.Count == 0))
                        //    nextCandidate.Add(tempList, supp);

                    }
                    else continue;
                }
            }

 public List<string> CombineItems(List<string> firstList, List<string> 
                                                                secondList)
    {
        List<string> resList = new List<string>();
        int k = firstList.Count; // количесво элементов в наборе
        resList = firstList;
        resList.Add(secondList[k - 1]);

        //for(int i = 0; i < k - 1; i++)
        //{
        //    if (firstList[i] == secondList[i])
        //        resList.Add(firstList[i]);     
        //}

        //if (resList.Count == k - 1)
        //    resList.Add(secondList[k - 1]);


        return resList;  
    }

Answer 1

Думаю как то так (пояснения в коде)

public static class Helper
{
    /// <summary>
    /// Возвращает список списков элементов переданного списка без повторений
    /// </summary>
    /// <typeparam name="T">Тип элементов</typeparam>
    /// <param name="list">Исходный список</param>
    /// <returns></returns>
    public static IList<IList<T>> GetAllOptionsWithoutRepetition<T>(this List<T> list)
    {
        // для хранения двоичных чисел
        var templates = new List<string>();
        // считаю сколько чисел будет в ответе и перевожу их в двоичные, начиная с 0
        for (int i = 0; i < Math.Pow(2,list.Count); i++)
        {
            var bin = Convert.ToString(i, 2);
            // так же дополняю нулями спереди для полноты двоичного числа
            templates.Add($"{"0".Repeat(list.Count - bin.Length)}{bin}");
        }

        // будущий результат
        var resAll = new List<IList<T>>();

        foreach(var template in templates)
        {
            var res = new List<T>();
            for (int ch = 0; ch < template.Length; ch++)
            {
                // если что-то должно стоять на этом месте, то ставлю (в соответсвиии с положением во входящем массиве)
                if (template[ch] == '1') res.Add(list[ch]);
            }
            // если массив не пустой, то добавляю к основному результату
            if (res.Count > 0) resAll.Add(res);
        }

        // возвращаю реузльтат, слортируя его ля красивости
        return resAll.OrderBy(s => s.Count).ThenBy(s => String.Join(" ",s)).ToList();
    }

    /// <summary>
    /// Возвращает n раз одну и ту же строку
    /// </summary>
    /// <param name="str">Строка</param>
    /// <param name="num">Количество повторений</param>
    /// <returns></returns>
    public static string Repeat(this string str,int num)
    {
        string result = string.Empty;
        for (int i = 0; i < num; i++)
        {
            result += str;
        }
        return result;
    }
}

Тест:

    List<string> l = new List<string> { "A", "B", "C" };
    var test = l.GetAllOptionsWithoutRepetition();
    foreach(var strs in test)
    {
        Console.WriteLine(String.Join(", ", strs));
    }

Результат:

Ваш тест:

    List<string> l = new List<string> { "bread", "milk", "chips", "mustard" };
    var test = l.GetAllOptionsWithoutRepetition();
    foreach (var strs in test)
    {
        Console.WriteLine(String.Join(", ", strs));
    }

Вывод:

БЛОГ НА HUSL

Как получить все возможные подсписки у списка? C#

Ответы (1 шт):