使用另一个数组的元素生成由一个数组定义的所有分区 [英] Generate all partitions, defined by one array, with elements of another array

问题描述

我试图找到数组元素的所有分区，但有一个重要的变化:

<块引用>

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

给定这两个数组:

left = [A, B];右 = [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]右 = [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 = []等等等等等等

解决方案

任意参数的解决方案(只要结果是可数的):

编辑:此版本避免了 len = Math.pow(left.length, right.length) 可能出现的问题以及长度超过 36 (cnr!) 的问题.

示例:

<块引用>

combine(['A', 'B'], [1, 2, 3]) 所有可能的行都是 2^3 = 8.在这个例子中，分布是二进制的，但它用更多的left参数改变了基数.

 发行版包含在集合中我 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 }

<块引用>

0 1 1 的分布 i = 3 计算为:

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.

 发行版包含在集合中我 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) {功能进位(){返回 c.reduceRight(function (r, _, i, o) {返回 r & &!(o[i] = (o[i] + 1) % left.length);}, 1);}var c = Array.apply(null, { length: right.length }).map(function () { return 0; }),结果 = [];做 {result.push(c.reduce(function (r, a, i) {r[left[a]].push(right[i]);返回 r;}, left.reduce(function (r, a) {r[a] = [];返回 r;}, {})));} while (!carry());返回结果；}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]), 空, 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>

I am trying to find all the partitions of the elements of an array, 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.

Given these two arrays:

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

I expect a collection of the following results:

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]

Edit:

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

Given 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.

解决方案

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!).

Example:

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 }

The distribution i = 3 of 0 1 1 evaluates as:

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.

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屋！