生成由一个数组定义的所有分区，其中包含另一个数组的元素

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.

任何参数的解(只要结果是可数的):

Edit:此版本避免了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 }

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

1. 取第一个0作为左侧left[0] = A的索引，移动右侧right[0] = 1 0的位值为a。
2. 取第二个1作为左侧left[1] = B的索引，将右侧right[1] = 2 1的位值移动到集合b。
3. 取第三个1作为左侧left[1] = B的索引，将右侧right[2] = 3 2的位值移动到集合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>

我的建议是试着写出你想要的代码:

function clone(arr) {
  var copy = new Array(arr.length);
  for (var i=0; i<arr.length; i++){
    copy[i] = new Array();
    for (var j=0; j<arr[i].length; j++)
      copy[i][j] = arr[i][j];
  }
  return copy;
}
function f(left,right){
  var result = [];
  function _f(left,i){
    if (i == right.length){
      result.push(left);
      return;
    }
    for (var j=0; j<left.length; j++){
      var _left = clone(left);
      _left[j].push(right[i]);
      _f(_left,i + 1);
    }
  }
  _f(left,0);
  return result;
}
console.log(JSON.stringify(f([[],[]],[1,2,3])));
console.log(JSON.stringify(f([[],[],[]],[1,2,3])));

输出:

"[[[1,2,3],[]],[[1,2],[3]],[[1,3],[2]],[[1],[2,3]],[[2,3],[1]],[[2],[1,3]],[[3],[1,2]]
,[[],[1,2,3]]]" 
"[[[1,2,3],[],[]],[[1,2],[3],[]],[[1,2],[],[3]],[[1,3],[2],[]],[[1],[2,3],[]]
,[[1],[2],[3]],[[1,3],[],[2]],[[1],[3],[2]],[[1],[],[2,3]],[[2,3],[1],[]],[[2],[1,3],[]]
,[[2],[1],[3]],[[3],[1,2],[]],[[],[1,2,3],[]],[[],[1,2],[3]],[[3],[1],[2]],[[],[1,3],[2]]
,[[],[1],[2,3]],[[2,3],[],[1]],[[2],[3],[1]],[[2],[],[1,3]],[[3],[2],[1]],[[],[2,3],[1]]
,[[],[2],[1,3]],[[3],[],[1,2]],[[],[3],[1,2]],[[],[],[1,2,3]]]"

我想我想出了一个可能的解决方案，但我确定它远非efficiënt。

给定数组:

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

首先创建一个power set right:

[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

然后对左中的每个值进行嵌套循环。每个循环将检查值是否已经在前一个循环中，最后一个循环也将检查是否所有值都存在。

在psuedo中，它看起来像这样:

for x in powerset
    a = x
    for y in powerset
        if y not in x
            b = y
            for z in powerset
                if z not in y and z not in x and [x + y + z] = right
                    c = z
                    displayresult

编辑

这是一个蹩脚低效的javascript解决方案。把它贴出来是为了完成。

https://jsfiddle.net/6o03d3L3/

function loop(left, right, powerSet, depth, siblings) {
    for (var i=0; i<powerSet.length; i++) {
        var values = powerSet[i];
        var isValueUsed = false;
        for (var k = 0; k < values.length; k++) {
            for (var l = 0; l < siblings.length; l++) {
                for (var m = 0; m < siblings[l].right.length; m++) {
                    if (values[k] === siblings[l].right[m]) {
                        isValueUsed = true;
                        break;
                    }
                }
                if (isValueUsed) {
                    break;
                }
            }
            if (isValueUsed) {
                break;
            }
        }
        if (!isValueUsed) {
            var result = { };
            result.left = left[depth];
            result.right = values;
            var results = siblings.slice();
            results.push(result);
            if (depth < left.length - 1) {
                loop(left, right, powerSet, depth + 1, results);
            } else {
                var valueCount = 0;
                for (var j = 0; j < results.length; j++) {
                    valueCount += results[j].right.length;
                }
                if (valueCount == right.length) {
                    log(results);
                }
            }
        }
    }
}

我相信您的问题可以这样改写:生成左侧中所有可能的标签分配到右侧中的元素。这是一个标准的回溯问题。

解的个数是l^r(因为你可以为每个元素独立地分配任何标签)，其中l是左中的元素个数，r是右中的元素个数。

我将提供一个递归的解决方案，也许你可以用一种非递归的方式重写，尽管它不会降低算法的复杂性(可能是常数)。实际上没有办法降低复杂性，因为在某些时候您需要生成每个解决方案。所以不要测试l=20和r=20，尝试更小的数字:p

// sol keeps the labels assigned to the elements in right
public static int[] sol = new int[r];
public static void generate(int p)
{
    for (int i=0;i<l;i++)
    {
        sol[p] = i;
        if (p==r-1)
        {
            // a solution is ready
            outputSolution(sol);
        }
        else
        {
            // still generating a solution
            generate(p+1);
        }
    }
}
// from where you need the results
generate(0);

只是为了说明，这是@NinaScholz的一个版本不使用toString进行基本转换或手动实现计数。我保留了结构代码相同。values.length-i-1可以只是"i"，但是我也想保持输出的顺序不变。

var combine = function(names, values){
    var result = [],
        max = Math.pow(names.length, values.length),
        m;
    for(m=0; m<max; m+=1){
        result.push(values.reduce(function(buckets, v, i){
            var nidx = Math.floor(m / Math.pow(names.length, values.length-i-1)) % names.length;
            buckets[names[nidx]].push(v);
            return buckets;
        }, names.reduce(function(a,v){
            a[v] = [];
            return a;
        }, {})));
    }
    return result;
};
document.getElementById('out').innerHTML = JSON.stringify(
        combine(Array.apply(null, Array(50)).map(function(_,i){ return i; }), [1,2]),
        null,
        4);

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