生成所有可能的组合

Question

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

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

固定数字的示例,

    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

当然可以.使用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();
}

十分简单!

Answer 2

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 3

替代方案:

第一步:阅读我关于如何生成与上下文敏感语法匹配的所有字符串的系列文章:

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

显然,您可以轻松地从两个数组生成该语法定义字符串.然后将其提供给代码,该代码生成给定语法中的所有字符串,然后就完成了; 你将获得所有可能性.(请注意,不一定按照你想要的顺序.)

Answer 4

使用Enumerable.Append.NET Framework 4.7.1 中添加的 ，可以实现 @EricLippert 的答案，而无需在每次迭代时分配新数组：

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>
    (this IEnumerable<IEnumerable<T>> enumerables)
{
    IEnumerable<IEnumerable<T>> Seed() { yield return Enumerable.Empty<T>(); }

    return enumerables.Aggregate(Seed(), (accumulator, enumerable)
        => accumulator.SelectMany(x => enumerable.Select(x.Append)));
}