找到两个数组的所有组合 [英] Find all combinations of two arrays

问题描述

我试图找到两个数组的所有组合，但有一个重要的变化：

I am trying to find all the combination of two arrays, but with an important variation:

第二个数组的每个值都需要分散在第一个的价值观上。所以总是使用第二个数组的所有值。

Each value of the second array needs to be spread out over the values of the first. So all values of the second array are always used.

给定这两个数组：

left = [A, B];
right = [1, 2, 3];

我期待收集以下结果：

A = [1, 2, 3]
B = []

A = [1, 2]
B = [3]

A = [1, 3]
B = [2]

A = [2, 3]
B = [1]

A = [1]
B = [2, 3]

A = [2]
B = [1, 3]

A = [3]
B = [1, 2]

A = []
B = [1, 2, 3]

编辑：

所以要清楚。这需要扩展两个数组。

So just to be clear. This needs to scale for both arrays.

给定数组：

left = [A, B, C, D]
right = [1, 2, 3, 4, 5, 6]

一些（许多可能的）结果将是：

Some of the (many, many possible) results would be:

A = [2, 5]
B = [1]
C = []
D = [3, 4, 6]

A = [6]
B = []
C = [1, 2, 3, 4, 5]
D = []

etc. etc. etc.

推荐答案

任何参数的解决方案（只要结果可数）：

编辑：此版本避免了可能出现的问题 len = Math.pow（left.length，right.length）和长度超过36的问题（cnr！）。

Solution for any parameter (as long as the result is countable):

Edit: This version avoids possible problems with len = Math.pow(left.length, right.length) and problems with length over 36 (cnr!).

combine（['A'，'B']，[1,2,3]）所有可能的行都是 2 ^ 3 = 8 。在此示例中，分布是二进制的，但它使用 left 的更多参数更改基数。

combine(['A', 'B'], [1, 2, 3]) all possible rows are 2^3 = 8. In this example, the distribution is binary, but it changes the base with more parameters of left.

  distribution      included in set
i       c            A           B   
----------------------------------------
0     0 0 0     { 1, 2, 3 } {         }
1     0 0 1     { 1, 2    } {       3 }
2     0 1 0     { 1,    3 } {    2    }
3     0 1 1     { 1       } {    2, 3 }
4     1 0 0     {    2, 3 } { 1       }
5     1 0 1     {    2    } { 1,    3 }
6     1 1 0     {       3 } { 1, 2    }
7     1 1 1     {         } { 1, 2, 3 }

分配 i = 3 of 0 1 1 评估为：

1. 取第一个 0 并将其作为左左[0] = A 的索引并移动 0 右边右[0] = 1 设置A.


2. Take第二个 1 并将其作为左左[1] = B 的索引并移动 1 右右[1] = 2 设置B.


3. 取第三个 1 并将其作为左左[1] = B 的索引并移动 2 的位置值右右[2] = 3 设置B。

1. Take the first 0 and take it as index of left left[0] = A and move the place value of 0 of right right[0] = 1 to set A.
2. Take the second 1 and take it as index of left left[1] = B and move the place value of 1 of right right[1] = 2 to set B.
3. Take the third 1 and take it as index of left left[1] = B and move the place value of 2 of right right[2] = 3 to set B.

另一个例子：

combine（['A'，'B'，'C']，[1,2] ）所有可能的行都是3 ^ 2 = 9.

Another example:

combine(['A', 'B', 'C'], [1, 2]) all possible rows are 3^2 = 9.

  distribution     included in set
i      c          A        B       C
----------------------------------------
0     0 0     { 1, 2 } {      } {      }
1     0 1     { 1    } {    2 } {      }
2     0 2     { 1    } {      } {    2 }
3     1 0     {    2 } { 1    } {      }
4     1 1     {      } { 1, 2 } {      }
5     1 2     {      } { 1    } {    2 }
6     2 0     {    2 } {      } { 1    }
7     2 1     {      } {    2 } { 1    }
8     2 2     {      } {      } { 1, 2 }

function combine(left, right) {

    function carry() {
        return c.reduceRight(function (r, _, i, o) {
            return r && !(o[i] = (o[i] + 1) % left.length);
        }, 1);
    }

    var c = Array.apply(null, { length: right.length }).map(function () { return 0; }),
        result = [];

    do {
        result.push(c.reduce(function (r, a, i) {
            r[left[a]].push(right[i]);
            return r;
        }, left.reduce(function (r, a) {
            r[a] = [];
            return r;
        }, {})));
    } while (!carry());
    return result;
}
document.getElementById('out').innerHTML = 
    "combine(['A', 'B'], [1, 2, 3]) = " + JSON.stringify(combine(['A', 'B'], [1, 2, 3]), null, 4) + '\n'+
    "combine(['A', 'B', 'C'], [1, 2] = " + JSON.stringify(combine(['A', 'B', 'C'], [1, 2]), null, 4) +'\n'+
    "combine(['A', 'B', 'C'], [1, 2, 3] = " + JSON.stringify(combine(['A', 'B', 'C'], [1, 2, 3]), null, 4) +'\n'+
    "combine(['A', 'B', 'C', 'D'], [1, 2, 3, 4, 5, 6]) = " + JSON.stringify(combine(['A', 'B', 'C', 'D'], [1, 2, 3, 4, 5, 6]), null, 4);

<pre id="out"></pre>

这篇关于找到两个数组的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！