为字符串列表生成所有组合

我想生成一个字符串列表的所有可能组合的列表(它实际上是一个对象列表,但为了简单起见,我们将使用字符串)。 我需要这个列表,以便我可以在unit testing中测试每个可能的组合。

例如,如果我有一个列表:

var allValues = new List() { "A1", "A2", "A3", "B1", "B2", "C1" } 

我需要一个List<List>其中包含以下所有组合:

  A1 A2 A3 B1 B2 C1 A1 A2 A1 A2 A3 A1 A2 A3 B1 A1 A2 A3 B1 B2 A1 A2 A3 B1 B2 C1 A1 A3 A1 A3 B1 etc... 

递归函数可能是获得所有组合的方法,但它似乎比我想象的更难。

有什么指针吗?

谢谢。

编辑:两个解决方案,有或没有递归:

 public class CombinationGenerator { public IEnumerable<List> ProduceWithRecursion(List allValues) { for (var i = 0; i < (1 < allValues[n]).ToList(); } } private IEnumerable ConstructSetFromBits(int i) { var n = 0; for (; i != 0; i /= 2) { if ((i & 1) != 0) yield return n; n++; } } public List<List> ProduceWithoutRecursion(List allValues) { var collection = new List<List>(); for (int counter = 0; counter < (1 << allValues.Count); ++counter) { List combination = new List(); for (int i = 0; i < allValues.Count; ++i) { if ((counter & (1 << i)) == 0) combination.Add(allValues[i]); } // do something with combination collection.Add(combination); } return collection; } } 

您可以使用n位二进制数自然对应于n元素集的子集这一事实手动进行。

 private IEnumerable constructSetFromBits(int i) { for (int n = 0; i != 0; i /= 2, n++) { if ((i & 1) != 0) yield return n; } } List allValues = new List() { "A1", "A2", "A3", "B1", "B2", "C1" }; private IEnumerable> produceEnumeration() { for (int i = 0; i < (1 << allValues.Count); i++) { yield return constructSetFromBits(i).Select(n => allValues[n]).ToList(); } } public List> produceList() { return produceEnumeration().ToList(); } 

如果您想要所有变体,请查看此项目以了解它是如何实现的。

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-CG

但你可以使用它,因为它是CPOL下的开源。

例如:

 var allValues = new List() { "A1", "A2", "A3", "B1", "B2", "C1" }; List result = new List(); var indices = Enumerable.Range(1, allValues.Count); foreach (int lowerIndex in indices) { var partVariations = new Facet.Combinatorics.Variations(allValues, lowerIndex); result.AddRange(partVariations.Select(p => String.Join(" ", p))); } var length = result.Count; // 1956 

Simillar的任务在以下post中得出:

列出字符串/整数的所有排列

希望这有帮助。

一个递归解决方案。 从以下代码中的AllCombinations ,您将获得所有可能的组合。 逻辑:

  1. 从一个元素开始。
  2. 生成所有可能的组合。
  3. 移至下一个元素,然后再次从步骤2开始。

码:

 public class Combination { private IEnumerable list { get; set; } private int length; private List> _allCombination; public Combination(IEnumerable _list) { list = _list; length = _list.Count(); _allCombination = new List>(); } public IEnumerable> AllCombinations { get { GenerateCombination(default(int), Enumerable.Empty()); return _allCombination; } } private void GenerateCombination(int position, IEnumerable previousCombination) { for (int i = position; i < length; i++) { var currentCombination = new List(); currentCombination.AddRange(previousCombination); currentCombination.Add(list.ElementAt(i)); _allCombination.Add(currentCombination); GenerateCombination(i + 1, currentCombination); } } }