.net - 生成 IEnumerable(Of T) 元素的所有唯一组合

Question

这个问题实际上和this SO post是一样的，只有我在寻找 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)。

就其值(value)而言，这不是家庭作业；尽管它确实有这种感觉。

编辑:更新了示例，因此结果看起来不像是按字母顺序排序的，以强调源 IEnumerable(Of T) 的现有顺序已被使用，并添加了第四个选项来阐明每组内的排序要求。

Answer 1

这是一个纯 Linq 解决方案，灵感来自 Eric Lippert 的 blog post关于计算笛卡尔积。我稍微修改了 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; }
}

可能比以前的版本效率更低，但它完成了工作...