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

Question

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

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

示例组合：

[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)])

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

Answer 1

这会生成所需结果的所有可能排列，因此它不会回答问题。

 function* combinations(combos) {
    yield combos;
    for(const [i1, group] of combos.entries()) {
       for(const [i2, group2] of combos.slice(i1 + 1).entries()) {
          if(group.some(v => group2.includes(v))) continue;
          yield* combinations([
            ...combos.filter((_, index) => index !== i1 && index !== i2), 
            [...group, ...group2]
         ]);
       }
    }
}

 console.log([...combinations([1, 2, 3, 4, 1].map(v => ([v])))]);

你可以从一个只包含一个元素的组合的数组开始，然后遍历这些组合并合并它们的两个数组，递归地进行。

Playground

Answer 2

您可以通过枚举所有可能的组合，然后找到每个组合的排列，然后过滤元素以确保它们是唯一的来做到这一点。这种过滤可以通过插入到集合中来完成。

子集函数来自@le_m ().

function* subsets(array, offset = 0) {
  while (offset < array.length) {
    let first = array[offset++];
    for (let subset of subsets(array, offset)) {
      subset.push(first);
      yield subset;
    }
  }
  yield [];
}

function* permutations(elements) {
  if (elements.length === 1) {
    yield elements;
  } else {
    let [first, ...rest] = elements;
    for (let perm of permutations(rest)) {
      for (let i = 0; i < elements.length; i++) {
        let start = perm.slice(0, i);
        let rest = perm.slice(i);
        yield [...start, first, ...rest];
      }
    }
  }
}

const arr = ['A', 'a', 'B', 'b', 'C', 'c', 'd', 'e'];
const results = new Set();

for (let subset of subsets(arr)) {
  if (subset.length) {
    for (let permut of permutations(subset)) {
       results.add(permut.join(''));
    }
  }
}

console.log([...results]);

Answer 3

您可以先将相同的元素分组并对其进行计数，结果 table 如下所示：

 1 | 2 | 3 | 4
 1 |    | 3 | 4
 1

(1重复两次，3和4重复一次)

现在您可以开始并取出前四个元素，然后是第二行中的 3 个元素，然后是最后一行中的一个元素，结果是

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

现在要得到下一个组合，只需从第一行中取出 3，然后让其他值向上移动：

 1 |   | 3 | 4
 1 |   |    | 4

现在再次取出行，你得到

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

现在对第一行重复此模式（取 2、1）等等，也对行重复此操作，然后您应该会得到想要的结果。

 const counts = new Map;

 for(const value of  [1, 1, 1, 2, 3, 3, 4, 4])
   counts.set(value, (counts.get(value) || 0) + 1);

 const result = [];

 for(let combo = 0; combo < counts.size; combo++) {
   const subResult = [];
   const combos = [...counts];
   for(let i = 0; i <= combo; i++) combos[i][0] -= 1;
   subResult.push(combos.slice(0, combo).map(([_, value]) => value);
   while(combos.some(([count]) => count > 0)) {
      subResult.push(combos.filter(([count]) => count > 0).map(([_, value] => value));
   }
   result.push(subResult);
}

Answer 4

从头开始实施算法：

获取字母出现的频率，
从密钥长度开始向下计算到 1
当频率图不为空时
- 将密钥添加到子结果中

const decrementKey = (o, k) => o[k]--;
const isEmpty = (o) => Object.keys(o).length === 0;
const removeKeys = (o) => Object.keys(o).forEach(k => { if (o[k] < 1) delete o[k]; });
const frequencyMap = (a) => a.reduce((r, v) => Object.assign(r, { [v] : (r[v] || 0) + 1 }), {});
const cloneMap = (o) => Object.keys(o).reduce((r, k) => Object.assign(r, { [k] : o[k] }), {});

let myArray = ["A", "A", "B", "B", "C", "C", "D", "E"];
let groups = solve(myArray);

console.log(groups.map(g => g.map(a => a.join('')).join(' | ')).join('\n'));

function solve(arr) {
  let freq = frequencyMap(arr), results = [];
  for (let max = Object.keys(freq).length; max > 1; max--) {
    let result = [], clone = cloneMap(freq);
    while (!isEmpty(clone)) {
      result.push(Object.keys(clone).reduce((res, key, index) => {
        if (index < max) {
          decrementKey(clone, key);
          res.push(key);
        }
        return res;
      }, []));
      removeKeys(clone);
    }
    if (result.length > 0) results.push(result);
  }
  return results;
}

.as-console-wrapper { top: 0; max-height: 100% !important; }

Answer 5

我得到了 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]]);

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

How to find all partitions of a multiset, where each part has distinct elements?

javascript

arrays

algorithm

combinations

combinatorics