生成所有可能的组合

给定2个数组Array1 = {a,b,c...n}和Array2 = {10,20,15....x}如何生成所有可能的组合作为stringa（i）b（j）c k）n（p）其中

 1 <= i <= 10, 1 <= j <= 20 , 1 <= k <= 15, .... 1 <= p <= x 

如：

 a1 b1 c1 .... n1 a1 b1 c1..... n2 ...... ...... a10 b20 c15 nx (last combination) 

所以在所有组合的总数中= array2 = (10 X 20 X 15 X ..X x)

类似于笛卡尔积，其中第二个数组定义了第一个数组中每个元素的上限。

以固定数字为例，

  Array x = [a,b,c] Array y = [3,2,4] 

所以我们会有3 * 2 * 4 = 24的组合。 结果应该是：

  a1 b1 c1 a1 b1 c2 a1 b1 c3 a1 b1 c4 a1 b2 c1 a1 b2 c2 a1 b2 c3 a1 b2 c4 a2 b1 c1 a2 b1 c2 a2 b1 c3 a2 b1 c4 a2 b2 c1 a2 b2 c2 a2 b2 c3 a2 b2 c4 a3 b1 c1 a3 b1 c2 a3 b1 c3 a3 b1 c4 a3 b2 c1 a3 b2 c2 a3 b2 c3 a3 b2 c4 (last) 

Answer 1

 using System; using System.Text; public static string[] GenerateCombinations(string[] Array1, int[] Array2) { if(Array1 == null) throw new ArgumentNullException("Array1"); if(Array2 == null) throw new ArgumentNullException("Array2"); if(Array1.Length != Array2.Length) throw new ArgumentException("Must be the same size as Array1.", "Array2"); if(Array1.Length == 0) return new string[0]; int outputSize = 1; var current = new int[Array1.Length]; for(int i = 0; i < current.Length; ++i) { if(Array2[i] < 1) throw new ArgumentException("Contains invalid values.", "Array2"); if(Array1[i] == null) throw new ArgumentException("Contains null values.", "Array1"); outputSize *= Array2[i]; current[i] = 1; } var result = new string[outputSize]; for(int i = 0; i < outputSize; ++i) { var sb = new StringBuilder(); for(int j = 0; j < current.Length; ++j) { sb.Append(Array1[j]); sb.Append(current[j].ToString()); if(j != current.Length - 1) sb.Append(' '); } result[i] = sb.ToString(); int incrementIndex = current.Length - 1; while(incrementIndex >= 0 && current[incrementIndex] == Array2[incrementIndex]) { current[incrementIndex] = 1; --incrementIndex; } if(incrementIndex >= 0) ++current[incrementIndex]; } return result; } 

Answer 2

当然可以 用LINQ做这件事有点棘手，但当然可能只使用标准的查询操作符。

更新：这是我的博客在2010年6月28日星期一的主题; 谢谢你的伟大的问题。 另外，我博客上的一位评论者指出，这个查询比我给出的查询更优雅。 我会在这里更新代码来使用它。

棘手的部分是使任意多个序列的笛卡尔乘积。 与之相比，在信件中“压缩”是微不足道的。 你应该研究这个，以确保你了解它是如何工作的。 每个部分都很简单，但是他们的组合方式需要一些习惯：

 static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) { IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>()}; return sequences.Aggregate( emptyProduct, (accumulator, sequence) => from accseq in accumulator from item in sequence select accseq.Concat(new[] {item}) ); } 

要解释这是如何工作的，首先要了解“累积”操作在做什么。 最简单的累加操作是“将这个序列中的所有东西加在一起”。 你这样做的方式是：从零开始。 对于序列中的每个项目，累加器的当前值等于累加器的项目和先前值之和。 我们正在做同样的事情，除了不是累计到目前为止的总和和当前项目的总和，我们正在积累笛卡尔乘积。

我们要这样做的方法是利用LINQ中已经有一个运算符来计算两件事情的笛卡尔乘积的事实：

 from x in xs from y in ys do something with each possible (x, y) 

通过在input序列中将累加器的笛卡尔乘积与下一项重复取出，并将结果稍作粘贴，就可以生成笛卡尔积。

所以想想累加器的价值。 为了便于说明，我将显示累加器的值作为其包含的序列运算符的结果 。 这不是累加器实际包含的内容。 累加器实际上包含的是产生这些结果的操作符 。 这里的整个操作只是build立了一个大量的序列算子树，其结果就是笛卡儿积。 但是直到执行查询之前，最终的笛卡尔积本身并不是实际计算的。 为了说明的目的，我将展示在每个阶段的结果是什么，但请记住，这实际上包含产生这些结果的操作符 。

假设我们正在取序列{{1, 2}, {3, 4}, {5, 6}}序列的笛卡尔乘积。 累加器以包含一个空序列的序列开始： { { } }

在第一次积累时，累加器是{{}}，项目是{1,2}。 我们这样做：

 from accseq in accumulator from item in sequence select accseq.Concat(new[] {item}) 

所以我们将{ { } }的笛卡尔乘积与{1, 2} ，并且对于每一对我们都有一对({ }, 1) ，所以我们连接{ }和{1}得到{1} 。 我们有一对({ }, 2}) ，所以我们连接{ }和{2}得到{2} 。 因此，我们有{{1}, {2}}作为结果。

所以在第二次累加时，累加器是{{1}, {2}} ，项目是{3, 4} 。 再一次，我们计算这两个序列的笛卡尔乘积得到：

  {({1}, 3), ({1}, 4), ({2}, 3), ({2}, 4)} 

然后从这些项目，将第二个连接到第一个。 所以结果是序列{{1, 3}, {1, 4}, {2, 3}, {2, 4}} ，这就是我们想要的。

现在我们再次积累。 我们用{5, 6}取累加器的笛卡尔乘积

  {({ 1, 3}, 5), ({1, 3}, 6), ({1, 4}, 5), ... 

然后连接第二个项目到第一个得到：

 {{1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6} ... } 

我们完成了。 我们已经积累了笛卡尔的产品。

现在我们有一个效用函数可以任意多个序列的笛卡尔乘积，其余的比较容易：

 var arr1 = new[] {"a", "b", "c"}; var arr2 = new[] { 3, 2, 4 }; var result = from cpLine in CartesianProduct( from count in arr2 select Enumerable.Range(1, count)) select cpLine.Zip(arr1, (x1, x2) => x2 + x1); 

现在我们有一系列的string序列，每行一个string序列：

 foreach (var line in result) { foreach (var s in line) Console.Write(s); Console.WriteLine(); } 

十分简单！

Answer 3

替代scheme：

第一步：阅读我的系列文章，了解如何生成符合上下文敏感语法的所有string：

http://blogs.msdn.com/b/ericlippert/archive/tags/grammars/

第二步：定义一个生成你想要的语言的语法。 例如，你可以定义语法：

 S: a A b B c C A: 1 | 2 | 3 B: 1 | 2 C: 1 | 2 | 3 | 4 

显然你可以很容易地从你的两个数组中生成这个语法定义string。 然后将其馈送到代码中，该代码将生成给定文法中的所有string，然后完成; 你会得到所有的可能性。 （并不是按照你想要的顺序存在，请注意。）

Answer 4

为了比较，这里是用Python来做的一个方法

 from itertools import product X=["a", "b", "c"] Y=[3, 4, 2] terms = (["%s%s"%(x,i+1) for i in range(y)] for x,y in zip(X,Y)) for item in product(*terms): print " ".join(item) 

Answer 5

Fon另一个解决scheme不是LINQ的基础，你可以使用：

 public class CartesianProduct<T> { int[] lengths; T[][] arrays; public CartesianProduct(params T[][] arrays) { lengths = arrays.Select(k => k.Length).ToArray(); if (lengths.Any(l => l == 0)) throw new ArgumentException("Zero lenght array unhandled."); this.arrays = arrays; } public IEnumerable<T[]> Get() { int[] walk = new int[arrays.Length]; int x = 0; yield return walk.Select(k => arrays[x++][k]).ToArray(); while (Next(walk)) { x = 0; yield return walk.Select(k => arrays[x++][k]).ToArray(); } } private bool Next(int[] walk) { int whoIncrement = 0; while (whoIncrement < walk.Length) { if (walk[whoIncrement] < lengths[whoIncrement] - 1) { walk[whoIncrement]++; return true; } else { walk[whoIncrement] = 0; whoIncrement++; } } return false; } } 

你可以在这里find一个如何使用它的例子。

Answer 6

我不愿意给你完整的源代码。 所以这是背后的想法。

您可以通过以下方式生成元素：

我假设A=(a1, a2, ..., an)和B=(b1, b2, ..., bn) （所以A和B每个都有n元素）。

然后recursion地做！ 写一个方法，需要一个和一个B并做你的东西：

如果A和B每个都只包含一个元素（称为resp.bn），只需从1迭代到bn并将其连接到您的迭代variables。

如果A和B每个都包含多于一个元素，则抓取第一个元素（ a1和b1 ），从1迭代到bn ，并为每个迭代步骤执行：

• 以A和B的子场从第二个元素开始，即A'=(a2, a3, ..., an) resp B'=(b2, b3, ..., bn)recursion地调用该方法。 对于recursion调用生成的每个元素，连接a1 ，迭代variables和recursion调用中生成的元素。

在这里你可以find一个如何在C＃中生成事物的琐事例子，你“只是”必须适应你的需求。

Answer 7

如果我正确地做到了，那么就是在笛卡尔产品之后 。 如果是这种情况，那么你如何使用LINQ来做到这一点。 可能不是确切的答案，但试图得到这个想法

---

  char[] Array1 = { 'a', 'b', 'c' }; string[] Array2 = { "10", "20", "15" }; var result = from i in Array1 from j in Array2 select i + j; 

---

这些文章可能有帮助

• 的SelectMany

• 如何使用LINQ SelectMany

Answer 8

finalResult是所需的数组。 假定两个arrays的大小相同。

 char[] Array1 = { 'a', 'b', 'c' }; int[] Array2 = { 3, 2, 4 }; var finalResult = new List<string>(); finalResult.Add(String.Empty); for(int i=0; i<Array1.Length; i++) { var tmp = from a in finalResult from b in Enumerable.Range(1,Array2[i]) select String.Format("{0} {1}{2}",a,Array1[i],b).Trim(); finalResult = tmp.ToList(); } 

我觉得这样就够了。

Answer 9

这是一个JavaScript版本，我相信有人可以转换。 它已经过彻底的testing。

这是小提琴 。

 function combinations (Asource){ var combos = []; var temp = []; var picker = function (arr, temp_string, collect) { if (temp_string.length) { collect.push(temp_string); } for (var i=0; i<arr.length; i++) { var arrcopy = arr.slice(0, arr.length); var elem = arrcopy.splice(i, 1); if (arrcopy.length > 0) { picker(arrcopy, temp_string.concat(elem), collect); } else { collect.push(temp_string.concat(elem)); } } } picker(Asource, temp, combos); return combos; } var todo = ["a", "b", "c", "d"]; // 5 in this set var resultingCombos = combinations (todo); console.log(resultingCombos); 

Answer 10

我刚刚发现这个CodeProject发布，其中包括Facets.Combinatorics命名空间，其中包含一些有用的代码来处理C＃中的Permuations，组合和变体。

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

Answer 11

Fon另一个解决scheme不是LINQ的，更有效：

 static IEnumerable<T[]> CartesianProduct<T>(T[][] arrays) { int[] lengths; lengths = arrays.Select(a => a.Length).ToArray(); int Len = arrays.Length; int[] inds = new int[Len]; int Len1 = Len - 1; while (inds[0] != lengths[0]) { T[] res = new T[Len]; for (int i = 0; i != Len; i++) { res[i] = arrays[i][inds[i]]; } yield return res; int j = Len1; inds[j]++; while (j > 0 && inds[j] == lengths[j]) { inds[j--] = 0; inds[j]++; } } }