生成的IEnumerable（Of T）中的所有元素的唯一组合 [英] Generate All Unique Combinations of Elements of a IEnumerable(Of T)

问题描述

这个问题几乎是一样的这太帖子，只有我寻找VB.NET（.NET 4）解决方案。我纺我的车轮足够长的时间试图想出一个通用的解决方案来解决这个权力集中的问题。

This question is virtually the same as this SO post, only I'm looking for a VB.NET (.NET 4) solution. I've spun my wheels long enough trying to come up with a generic solution to solving this "power set" problem.

由于：

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

我在寻找 choiceSets 是一个的IEnumerable（中的IEnumerable中（T））让我可以这样做：

I'm looking for choiceSets to be an IEnumerable(Of IEnumerable(Of T)) so that I can do something like:

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）已的顺序，并在列表中的每个产品> =中的项目数量方面的previous项目在内的IEnumerable（Of T）已。

As you can see, this is every non-repeating combination from the source IEnumerable(Of T) (which could have 1 to many items in it - this example only had 4), it operates based on the order of the items in the source IEnumerable(Of T), and each item in the list is >= the previous item in terms of number of items in the inner IEnumerable(Of T).

有关它的价值，这是不是作业;尽管它肯定不会觉得它。

For what it's worth, this is not homework; though it sure does feel like it.

编辑：更新这个例子，它看起来并不像结果按字母顺序排序，强调的是源的IEnumerable（Of T）已现有顺序使用，增加了第四选择，弄清楚每个组内的排序要求。

Updated the example so it does not look like the result is alphabetically sorted, to stress that the source IEnumerable(Of T)'s existing order is used and added a 4th choice to clarify the sorting requirement within each set.

推荐答案

下面是一个纯粹的LINQ的解决方案，灵感来自埃里克利珀的<一个href="http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx"相对=nofollow>博客文章如何计算笛卡尔乘积。我修改了 CartesianProduct 方法略显使其返回组合：

Here's a pure Linq solution, inspired by Eric Lippert's blog post about computing a cartesian product. I modified the CartesianProduct method slightly so that it returns combinations:

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

在此基础上扩展方法

，你就可以生产所需的结果如下：

Based on this extension method, you can produce the desired result as follows:

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项）

(it concatenates all combinations of 1, 2... N items)

请注意，这可能不是一个非常有效的解决方案，但我认为这是一个有趣的使用LINQ的...

Note that it's probably not a very efficient solution, but I think it's an interesting use of Linq...

编辑：这里的组合方法，它保持了原有秩序的新版本：

here's a new version of the Combinations method that maintains the original order:

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

也许甚至超过了previous版本低效的，但它能够完成任务......

Probably even more inefficient than the previous version, but it gets the job done...

这篇关于生成的IEnumerable（Of T）中的所有元素的唯一组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！