Генерация всех уникальных комбинаций элементов IEnumerable (Of T)

Question

Этот вопрос практически совпадает с этой публикацией SO , только я ищу решение VB.NET (.NET 4). Я крутил свои колеса достаточно долго, пытаясь найти общее решение для решения этой проблемы с «набором мощности».

Дано:

Dim choices As IEnumerable(Of String) = {"Coffee", "Tea", "Milk", "Cookies"}
Dim choiceSets = choices.CombineAll()

Я ищу choiceSets, чтобы быть IEnumerable(Of IEnumerable(Of T)), чтобы я мог сделать что-то вроде:

For each choiceSet in choiceSets
    Console.WriteLine(String.Join(", ", choiceSet))
Next

И получите результаты, которые выглядят так:

Coffee
Tea
Milk
Cookies
Coffee, Tea
Coffee, Milk
Coffee, Cookies
Tea, Milk
Tea, Cookies
Milk, Cookies
Coffee, Tea, Milk
Coffee, Tea, Cookies
Coffee, Milk, Cookies
Tea, Milk, Cookies
Coffee, Tea, Milk, Cookies

Как видите, это каждая неповторяющаяся комбинация из источника IEnumerable(Of T) (в которой может быть от 1 до многих элементов - в этом примере всего 4), она работает на основе порядок элементов в источнике IEnumerable(Of T), и каждый элемент в списке>> = предыдущий элемент с точки зрения количества элементов во внутреннем IEnumerable(Of T).

Для чего это стоит, это не домашняя работа; хотя это действительно так.

РЕДАКТИРОВАТЬ: обновил пример, чтобы он не выглядел так, как будто результаты отсортированы по алфавиту, чтобы подчеркнуть, что используется существующий порядок источника IEnumerable(Of T), и добавлен 4-й выбор, чтобы прояснить требование сортировки в каждом наборе.

Answer 1

Вот чистое решение Linq, вдохновленное блогом Эрика Липперта о вычислении декартового произведения. Я немного изменил метод CartesianProduct, чтобы он возвращал комбинации:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) => 
        from accseq in accumulator 
        // Exclude items that were already picked
        from item in sequence.Except(accseq)
        // Enforce ascending order to avoid same sequence in different order
        where !accseq.Any() || Comparer<T>.Default.Compare(item, accseq.Last()) > 0
        select accseq.Concat(new[] {item})).ToArray();
}

На основе этого метода расширения вы можете получить желаемый результат следующим образом:

IEnumerable<string> items = new[] {"Coffee", "Tea", "Milk"};
IEnumerable<IEnumerable<string>> result =
    Enumerable.Range(1, items.Count())
        .Aggregate(
            Enumerable.Empty<IEnumerable<string>>(),
            (acc, i) =>
                acc.Concat(Enumerable.Repeat(items, i).Combinations()));

(объединяет все комбинации из 1, 2 ... N элементов)

Обратите внимание, что это, вероятно, не очень эффективное решение, но я думаю, что это интересное использование Linq ...

---

РЕДАКТИРОВАТЬ: вот новая версия Combinations метода, который поддерживает первоначальный порядок:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    var indexedSequences = sequences.Select(seq => seq.Select((item, idx) => new IndexedItem<T>(item, idx)));
    IEnumerable<IEnumerable<IndexedItem<T>>> emptyProduct = new[] { Enumerable.Empty<IndexedItem<T>>() };
    var indexedResult =
        indexedSequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) => 
            from accseq in accumulator 
            // Exclude items that were already picked
            from item in sequence.Except(accseq)
            // Enforce ascending order of indexes to avoid same sequence in different order
            where !accseq.Any() || item.Index > accseq.Last().Index
            select accseq.Concat(new[] {item})).ToArray();
    return indexedResult.Select(seq => seq.Select(i => i.Item));
}

class IndexedItem<T>
{
    public IndexedItem(T item, int index)
    {
        this.Item = item;
        this.Index = index;
    }

    public T Item { get; private set; }
    public int Index { get; set; }
}

Возможно, даже более неэффективно, чем предыдущая версия, но она выполняет свою работу ...

Answer 2

Я нашел другой подход здесь (ищите там код C #).

    Public Function GetPowerSet(Of T)(items As IEnumerable(Of T)) As IEnumerable(Of IEnumerable(Of T))

         Dim result = From m In Enumerable.Range(0, 1 << items.Count)
                 Select
                    From i In Enumerable.Range(0, items.Count)
                    Where (m And (1 << i)) <> 0
                        Select items(i)
         Return result

End Function

Answer 3

В случае, если это кому-то пригодится, я конвертировал оригинальное расширение C #, опубликованное Томасом Левеском в VB.NET:

    <System.Runtime.CompilerServices.Extension()> _
    Public Function Combinations(Of T)(ByVal sequences As IEnumerable(Of IEnumerable(Of T))) As IEnumerable(Of IEnumerable(Of T))
        Dim seed As IEnumerable(Of IEnumerable(Of T)) = {  Enumerable.Empty(Of T) }
        Dim r = sequences.Aggregate(seed, 
             Function(ByVal accumulator, ByVal sequence) _
               From accseq In accumulator    _
               From item In sequence.Except(accseq) _
               Where (Not accseq.Any()) OrElse Comparer(Of T).Default.Compare(item, accseq.Last()) > 0  _
               Select accseq.Concat(  {item}  ) ).ToArray()
        Return r
    End Function

Немного неудобно использовать повторение n раз длясгенерировать повторное перечисление, содержащее множество всех возможных значений n раз, где n - количество элементов в каждой полученной уникальной комбинации T, но оно выполняет свою работу.Порядок результатов не имел для меня значения, поэтому я не конвертировал «проиндексированную» версию, размещенную позже.

Вот мое использование расширения, которое работает с массивом целых чисел, а не со строками, и дает мне «пустой» набор без элементов в нем и «полный» (или оригинальный) набор

    Dim allRolesArray  = {1,4,5,2,0}
    Dim comboCountValues = Enumerable.Range(0, allRolesArray.Count()+1)
    Dim allRoleCombos = comboCountValues.Aggregate(
        Enumerable.Empty(Of IEnumerable(Of Integer))(),
        Function (acc, i) acc.Concat(Enumerable.Repeat(allRolesArray, i).Combinations() ) ).ToList

Answer 4

IEnumerable<IEnumerable<string>> seed = new[] { Enumerable.Empty<string>() };

choices.Aggregate(
    seed,
    (acc, item) =>
        acc.SelectMany(a => new[] { a, a.Concat(new[] {item}) }))

или

choices.Aggregate(
    seed,
    (acc, item) =>
        from a in acc
        from c in new[] { Enumerable.Empty<string>(), new[] { item } }
        select a.Concat(c))

Answer 5

Я не программирую на VB.NET, и это просто набрано. Так что могут быть серьезные ошибки. Но подход должен работать.

static List<List<string>> GetChoiceSets(List<string> choices)
{
    int capacity = (int) Math.Pow(2, choices.Count()) - 1;
    int bit = 1;
    List<List<string>> choiceSets = new List<List<string>>(capacity);
    for (int i = 0; i < capacity; i++)
        choiceSets.Add(new List<String>());

    n = 0;
    for (int size = 1; size <= choices.Count(); size++)
    {
        List<int> indexes = new List<int>(size);
        for (int i = 0; i < size; i++)
            indexes.Add(i);

        // We break out after exhausting all sets of this size.
        for (;;) {
            // Insert solution.
            for (int i = 0; i < size; i++)
                choiceSets[n].Add(choices[indexes[i]]);
            n++;

            // Figure out the first place we can advance indexes.
            int j = 1;
            for (; j <= size; j++) {
                if (indexes[size - j] < choices.Count() - j) {
                    break;
                }
            }
            threshold = choices.Count() - j
            // Did we finish?
            if (threshold < 0)
                break;

            // We will increment the index at threshold, and make following ones
            // increment from there.
            indexes[threshold]++;
            for (int i = 1; i + threshold < choices.Count(); i++)
                indexes[threshold + i] = indexes[threshold] + i;
        }
    }

    return choiceSets;
}

Answer 6

Наивное рекурсивное решение (много накладных расходов на создание списка):

    static List<IEnumerable<string>> GetChoiceSets(IEnumerable<string> choices)
    {
        if (choices == null || !choices.Any())
            return null;
        else
        {
            var first = choices.Take(1);
            var inner = GetChoiceSets(choices.Skip(1));

            if (inner == null)
                return new List<IEnumerable<string>> { first, new List<string> { } };
            else
                return inner.Select(lst => first.Union(lst)).Union(inner).ToList();
        }
    }

Немного менее наивное итеративное решение с использованием алгоритма связанного SO:

    static List<List<string>> GetChoiceSets2(List<string> choices)
    {
        int capacity = (int)Math.Pow(2, choices.Count());
        int bit = 1;
        List<List<string>> choiceSets = new List<List<string>>(capacity);
        for (int i = 0; i < capacity; i++)
            choiceSets.Add(new List<String>());

        for (int i = 0; i < choices.Count(); i++)
        {
            for (int n = 0; n < capacity; n++)
            {
                if ((n & bit) == bit)
                    choiceSets[n].Add(choices[i]);
            }
            bit *= 2;
        }

        return choiceSets;
    }

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