生成 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)。

无论如何，这不是家庭作业；而是家庭作业。尽管感觉确实如此。

编辑：更新了示例，使其看起来不像结果按字母顺序排序，以强调使用源 IEnumerable(Of T) 的现有顺序，并添加了第四个选择来澄清排序要求每组内。

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 发布到 VB.NET 的原始 C# 扩展：

    <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 的集合的重复 Enumerable，这种用法有点尴尬次，其中 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))