生成所有可能的组合

Question

生成所有可能的组合

72

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

- Amitd

4

您能否给出一个更好的例子，使用更少的元素并产生完整的结果？例如，我有一个问题是第一个数组的每个元素是否仅应与第二个数组的对应元素配对，还是您想将其与第二个数组的所有元素组合在一起。 - Lasse V. Karlsen

可能数组的大小是相同的。 - Gulshan

是的，两个数组的大小相同。 - Amitd

8

Eric专门为您撰写了这篇博客 :) http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx - Ahmed

@Ahmed提到的帖子的更新链接：https://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/ - undefined

12个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NilNul · Answer 1

最受欢迎的答案非常出色，但并没有明确说明这实际上是将两个向量字符串连接起来，即使操作数是 IEnumerable<T>，它也应该被视为 IEnumerable<(T)>，即一个 1-元组的字符串。

为了使其在理论上（不一定在实践中）更美观，我建议按照以下方式实现：

首先，实现一个二元运算符：

public interface BinaryI<T>
{
    T op(T,T);
}

public class Cartesian<T> :BinaryI<IEnumerable<T>>
{
    public IEnumerable<IEnumerable<T>> op(IEnumerable<IEnumerable<T>> par, IEnumerable<IEnumerable<T>> par1)
    {
        return  from x in par
            from y in par1
            select x.Concat(y)
        ;
    }
}

然后将其扩展为累加器：

public class Cumulator<T,TOp> where TOp:BinaryI<T>
{
    private T _initial;
    public T initial { get { return _initial; } }
    private TOp _binder;
    public TOp binder { get { return _binder; } }
    public Cumulator(T initial, TOp binder)
    {
        _initial = initial;
        _binder = binder;
    }

    public T cumulate(IEnumerable<T> seq)
    {
        return  seq.Aggregate(initial, _binder.op);
    }
}

然后你可以使用它：

var accumulator = new Cumulator<IEnumerable<T>,BinaryI<T>>(new[]{Enumerable.Empty<T>()}, new Cartesian<T>());
cumulator.cumulate ((IEnumerable<IEnumerable<T>>) (something));

上述内容摘自我们的某些生产代码，并且为了这个答案，继承过程中的一些中间类型被缩短了。

- bob · Answer 2

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

这是fiddle的链接。

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