生成 IEnumerable(of T) 的所有唯一元素组合

Question

这个问题实际上与这篇文章相同，只是我正在寻找 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; }
}

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

Answer 2

如果它对其他人有用，我已经将 Thomas Levesque 发布的原始 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

必须调用 Repeat 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 3

我在这里找到了另一种方法（在那里查找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 4

一个朴素的递归解决方案（大量的列表创建开销）：

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

这些可能都可以改进，但根据正在使用的集合的大小，其中一个应该足够有效。

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

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))