javascript - 如何找到多重集的所有分区，其中每个部分都有不同的元素？

Question

假设我们有这样一个数组:myArray = [A, A, B, B, C, C, D, E]

我想创建一个算法，以便它可以找到加起来构成整个数组的所有组合，其中没有任何元素重复。

示例组合:

[A, B, C, D, E] [A, B, C]
[A, B, C, D] [A, B, C, E]
[A, B, C] [A, B, C] [D, E]

说明:[A, B, C] [A, B, C] [D, E] 和 [A, B, C] [D, E] [A, B, C] 是相同的组合。此外，子集的顺序也无关紧要。例如 [A,B,C] 和 [B,A,C] 应该相同。到目前为止，我没有超越

var myArray = ["A", "A", "B", "B", "C", "C", "D", "E"]

console.log([...new Set(myArray)])

但这根本没有帮助，它只是返回一个不同的集合。我找不到之前发布的类似问题，所以有人可以在这里指导我如何实现这一目标吗？

Answer 1

我得到了 315 种组合。是对的吗？ :)

这是一个递归:

function distribute(e, i, _comb){
  // No more e's
  if (e[1] == 0)
    return [_comb];
  // We're beyond the combination
  if (i == -1)
    return [_comb.concat([e])];
  let result = [];
  for (let c=1; c<=Math.min(_comb[i][1], e[1]); c++){
    let comb = _comb.map(x => x.slice());

    if (c == comb[i][1]){
      comb[i][0] += e[0];

    } else {
      comb[i][1] -= c;
      comb.push([comb[i][0] + e[0], c]);
    }
    result = result.concat(distribute([e[0], e[1] - c], i - 1, comb));
  }
  let comb = _comb.map(x => x.slice());
  return result.concat(distribute(e, i - 1, comb));
}

function f(arr){
  function g(i){
    if (i == 0)
      return [[arr[0]]];
    const combs = g(i - 1);
    let result = [];
    for (let comb of combs)
      result = result.concat(
        distribute(arr[i], comb.length - 1, comb));
    return result;
  }
  return g(arr.length - 1);
}

function show(arr){
  const rs = f(arr);
  const set = new Set();

  for (let r of rs){
    const _r = JSON.stringify(r);
    if (set.has(_r))
      console.log('Duplicate: ' + _r);
    set.add(_r);
  }

  let str = '';
  for (let r of set)
    str += '\n' + r
  str += '\n\n';

  console.log(JSON.stringify(arr));
  console.log(set.size + ' combinations:');
  console.log(str);
}

show([['A', 2], ['B', 2], ['C', 2], ['D', 1], ['E', 1]]);