來自不同羣體的特定順序的組合

Question

我有一個參數列表，每個參數都接受特定範圍的輸入。我正在創建一個測試，每創建一個可能的有效輸入。此外，每個組都是可選的（可以完全跳過），所以組合長度不一定必須與列表長度相同。每組

輸入

List<string[]> temp = new List<string[]> 
{ 
    // The order of these groups is important 
    new string[] { "a", "b", "c" }, 
    new string[] { "d", "e" }, 
    new string[] { "f", "g", "h" } 
}; 

約束

1. 0或1項（上方的string[]）的List<T>的
2. 順序必須保存

有效組合

1. a, e, f
2. a, d, g
3. c, e, f
4. b, g
5. c, f

無效組合

1. a, b, f（a和b來自同一組 - 不允許）
2. a, f, d（錯誤的命令 - d一定要來f前）

到目前爲止，我已經回到我的圖書館，在那裏我有一個組合LINQ方法。

public static class IEnumerableExtensions 
{ 
    // Can be used to get all permutations at a certain level 
    // Source: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n#1898744 
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k) 
    { 
     return k == 0 ? new[] { new T[0] } : 
      elements.SelectMany((e, i) => 
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c))); 
    } 
} 

在過去，我只用這個單個序列來做類似generate every permutation of URL segments的事情。但是我在使用嵌套列表時遇到了困難，每個組的約束條件都是按照特定的順序進行的。

我知道我可以通過做3個嵌套循環並使用列表來跟蹤哪些項目已經被使用，但我不知道List<T>中有多少項目，所以不會在一般情況下工作。如何獲得上述輸入的所有有效組合？

我寧願LINQ，但會接受解決此問題的任何解決方案。

Answer 1

使用一些擴展功能，

public static IEnumerable<T> Prepend<T>(this IEnumerable<T> rest, params T[] first) => first.Concat(rest); 
public static IEnumerable<T> AsSingleton<T>(this T source) { 
    yield return source; 
} 

你可以寫

public static IEnumerable<IEnumerable<T>> ParametersWithEmpty<T>(this IEnumerable<IEnumerable<T>> ParmLists) { 
    if (ParmLists.Count() == 0) 
     yield break; // empty 
    else { 
     var rest = ParametersWithEmpty(ParmLists.Skip(1)); 
     foreach (var p in ParmLists.First()) { 
      yield return p.AsSingleton(); // p.Concat(empty) 
      foreach (var r in rest) 
       yield return r.Prepend(p); // p.Concat(r) 
     } 
     foreach (var r in rest) 
      yield return r; // empty.Concat(r) 
    } 
} 

你可以這樣調用：

var ans = temp.ParametersWithEmpty(); 

要在結果中包括所有的水平，你必須跳過空的情況下，隱含在上面的代碼：

public static IEnumerable<IEnumerable<T>> Parameters<T>(this IEnumerable<IEnumerable<T>> ParmLists) { 
    if (ParmLists.Count() == 1) 
     foreach (var p in ParmLists.First()) 
      yield return p.AsSingleton(); 
    else { 
     var rest = Parameters(ParmLists.Skip(1)); 
     foreach (var p in ParmLists.First()) { 
      foreach (var r in rest) 
       yield return r.Prepend(p); 
     } 
    } 
} 

最後，這裏是一個替代版本，它可以使它更清晰一些，因爲它輸出的序列好像每個參數列表前面都是空的，但也會返回答案中的所有空序列。

​​

Answer 2

嘗試以下操作：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     public static List<string[]> temp = new List<string[]> 
     { 
      // The order of these groups is important 
      new string[] { "a", "b", "c" }, 
      new string[] { "d", "e" }, 
      new string[] { "f", "g", "h" } 
     }; 
     static void Main(string[] args) 
     { 
      Recursive(0, new List<string>()); 
      Console.ReadLine(); 
     } 
     public static void Recursive(int level, List<string> output) 
     { 
      if (level < temp.Count) 
      { 
       foreach (string value in temp[level]) 
       { 
        List<string> newList = new List<string>(); 
        newList.AddRange(output); 
        newList.Add(value); 
        Console.WriteLine(string.Join(",", newList)); 
        Recursive(level + 1, newList); 
       } 
      } 
     } 
    } 
} 

爲了獲得額外的組合開始，第二和第三級變化的main（）

 static void Main(string[] args) 
     { 
      for (int i = 0; i < temp.Count; i++) 
      { 
       Recursive(i, new List<string>()); 
      } 
      Console.ReadLine(); 
     } 

Answer 3

這是一個列舉所有組合的Linq表達式。你可以在online C# repl試試。想法是使用累加器「a」通過遍歷您的臨時集合「b」的每個項目來收集所有組合，並添加「b」（單項組合）的元素以及添加到迄今爲止累積的每個組合。雖然很毛茸茸的表情。

var combinations = temp.Aggregate(Enumerable.Empty<IEnumerable<string>>(), (a, b) => a 
      .Concat(b.Select(i => Enumerable.Repeat(i, 1))) 
      .Concat(a.SelectMany(i => b.Select(j => i.Concat(Enumerable.Repeat(j, 1))))));