生成所有可能的组合

给定2个数组Array1 = {a,b,c...n}和Array2 = {10,20,15....x}如何生成所有可能的组合作为字符串a（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)的元素乘积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)

---

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

---

当然。 用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)

通过反复将累加器的笛卡尔乘积与输入序列中的下一项进行比较，并将结果粘贴在一起，我们就可以生成笛卡儿乘积。

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

假设我们正在取序列{{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);

现在我们有一系列字符串序列，每行一个字符串序列：

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

十分简单！

---

替代方案：

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

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

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

链接地址: http://www.djcxy.com/p/37281.html

上一篇: Generating all Possible Combinations

下一篇: How to succinctly, portably, and thoroughly seed the mt19937 PRNG?