生成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)的现有订单并添加第4个选项以阐明每个集合中的排序要求。

Answer 1

这里是一个纯LINQ的解决方案，由Eric Lippert的blog post关于计算笛卡尔积启发。我修改了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项）

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

---

编辑：这里的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

一个天真的递归解决方案（批次列表创建开销）：使用链接SO算法

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

一个稍微不那么幼稚的迭代求解：

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 3

我不在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 4

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

Answer 5

在情况下，它使用的其他任何人，我已经转换原来的C＃扩展托马斯Levesque的发布到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 

这是一个有点尴尬的使用有来电重复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 6

我发现另一个approach here（查看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