生成一个 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)的现有顺序并添加第四个选择以澄清每个集合内的排序要求。

- ckittel

---

请注意，IEnumerable<T> 不保证一致的排序，因此“遵守”它可能会因调用而异。 - dlev

@dlev 这很值得注意，谢谢。我认为即使假设IEnumerable<T>确保了一致的排序，这个问题仍然可以存在。让我们假装它确实是这样，以简化问题 :) - ckittel

你可以尝试这里的代码示例：http://www.codeproject.com/KB/recipes/Combinatorics.aspx - mellamokb

@mellamokb 感谢提供链接。实际上，我在开始研究这个问题时就看到了那篇文章的代码。对我来说，它似乎是一个过于复杂的解决方案，特别是当我看到类似组合问题的自包含扩展的示例时。如果没有其他人能够想出更简洁的解决方案，那么我的备选方案就是那篇文章的解决方案。 - ckittel

请注意，您要查找的是一个集合的“幂集”；即所有子集的集合。（幂集还包括空子集，但您可以忽略它。）如果您正在寻找此问题的解决方案，则了解其正确名称将会有所帮助。 - Eric Lippert

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

这个版本可能比以前的版本更加低效，但它能完成任务...

- Thomas Levesque

---

感谢您的输入。结果数量正确（我喜欢它甚至没有包括空集），但排序不符合问题陈述，但非常接近（迄今为止最接近的答案）。一旦将第四个项目添加到“items”中，排序规则明显崩溃。结果从上到下正确排序，但在集合内部排序不正确。我可以进行一些后处理排序，以使它们恢复到正确的顺序。 - ckittel

@ckittel，请看我的更新答案。我为每个项目关联了一个索引，以便我可以保持原始顺序。 - Thomas Levesque

A+。非常感谢！这个解决方案非常适合我的需求。我可能会在今天晚些时候自己撰写一个答案，以展示VB.NET版本，让其他人受益，但是这个解决方案绝对是被接受的答案。感谢您在解决方案中如此勤奋。 - ckittel

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次来生成一个重复的Enumerable，其中包含了T的所有可能值，并且n是每个结果唯一组合中元素的数量。但这样也可以完成任务。对于我而言，结果的顺序不重要，所以我没有转换后面发布的“indexed”版本。

以下是我使用该扩展的示例，它操作的是一个整数数组而不是字符串数组，并且能够获取不包含任何元素的“空”集合和完整（或原始）集合。

    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

- emu604

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

- habakuk

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

这两个方法都可以改进，但根据使用的集合大小，其中一个应该足够高效。

- mellamokb

---

谢谢，很好的开始。第一个解决方案没有按照指定的顺序返回它们，其中集合按大小（或保持不变）增加并保留顺序。我得到了[Coffee，Tea，Milk]，[Coffee，Tea]，[Coffee，Milk]，[Coffee]，[Tea，Milk]，[Tea]，[Milk]，[]。（最后还有一个空白项？）我将尝试第二个解决方案，看看它是否符合必要的要求。 - ckittel

看起来第二个解决方案也存在相同的排序要求差距（并且末尾也有空白项）。在这两种情况下，确实找到了正确的值，只是顺序不符合规范。 - ckittel

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

- btilly

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

- svick

---

感谢您的输入。结果数量正确，但排序不满足问题陈述。当您开始添加超过三个选项时，这将是非常不同的事实。 - ckittel