生成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解决方案,灵感来自Eric Lippert 关于计算笛卡尔积的博客文章.我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; }
}

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