找到两个数组的所有组合

Question

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

第二个数组的每个值都需要分散在第一个数组的值上.因此总是使用第二个数组的所有值.

鉴于这两个数组:

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]

编辑:

所以要清楚.这需要针对两个阵列进行扩展.

给定数组:

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

一些(许多可能的)结果将是:

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

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

etc. etc. etc.

Answer 1

任何参数的解决方案(只要结果可数)

编辑:这个版本避免了可能len = Math.pow(left.length, right.length)的问题和长度超过36(cnr!)的问题.

这个怎么运作:

示例:combine(['A', 'B'], [1, 2, 3])所有可能的行都是2 ^ 3 = 8.分布在此示例中为二进制,但是更多参数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的0 1 1计算结果为:

1. 取第一个0并将其作为左侧的索引left[0] = A并移动右侧的0的位置值right[0] = 1以设置A.
2. 取第二个1并将其作为左侧的索引left[1] = B并移动右侧的1的位置值right[1] = 2以设置B.
3. 取第三个1并将其作为左侧的索引left[1] = B并移动右侧的2的位置值right[2] = 3以设置B.

另一个例子:combine(['A', 'B', 'C'], [1, 2])所有可能的行都是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>