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

这个问题与 this SO post几乎相同,只是我在寻找VB.NET(.NET 4)解决方案.我已经足够长时间旋转我的车轮,试图想出一个解决这个“动力装置”问题的通用解决方案.

鉴于：

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

我正在寻找choiceSets是一个IEnumerable(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个选项以阐明每个集合中的排序要求.

这是一个纯粹的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 …

编辑：这是一个新版本的组合方法,维护原始顺序：

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

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