将数组（元素组合）划分为自定义分区的所有方法 [英] All ways of dividing an array (element combinations) into a custom partition

问题描述

我想将n个元素的数组划分为给定大小的子数组以及所有可能的元素组合。

I want to divide array of n elements to given size subarrays with all possible combinations of elements.

例如：

数组： {1,2,3,4} - 可以是n个元素，1< n< 100.它可以有重复。

Array: {1,2,3,4} - can be n elements, 1 < n < 100. It can have duplicates.

给定大小模式（只是示例，可能不同）： [2 -subarrays，2-elements]

Given size pattern (just example, could be different): [2 -subarrays, 2-elements]

预期结果：

{1,2 }，{3,4}

{1,3}，{2,4}

{1,4}，{2,3}

{1,2},{3,4}
{1,3},{2,4}
{1,4},{2,3}

或

{2,1}，{3,4}

{1,3}，{4,2}

{3,2}，{1,4}

{2,1},{3,4}
{1,3},{4,2}
{3,2},{1,4}

等。正如您所看到的，子数组中元素的顺序或子数组中子数组的顺序无关紧要。它必须是输入数组子阵列的最小数量。

etc.. As You can see, the order of elements in subarrays, or the order of subarrays in sets of subarrays does not matter. It has to be minimum number of sets of the input array subarrays.

我必须在解决方案之下，但它也包括排列。我需要对此进行优化，以便根本不生成任何排列。 JavaScript不是必需的，任何语言都可以。在此先感谢您的帮助。

I've got to below solution, but it includes also permutations. I need to optimize this to not generate any permutations at all. JavaScript is not necesarry, any language will do. Thanks in advance for any help.

function getN(n, array, subsets) {
    var f,
        l = array.length,
        indices = [],
        temp;

    array = array.slice();
    while (l--) {
        f = factorial(l);
        indices.push(Math.floor(n / f));
        n %= f;
    }
    temp = indices.map(i => array.splice(i, 1)[0]);
    return subsets
        ? subsets.map((i => l => temp.slice(i, i += l))(0))
        : temp;


}

function factorial(num) {
    var result = 1;
    while (num) {
        result *= num;
        num--;
    }
    return result;
}

var i, l,
    array = ['1', '2', '3', '4'],
    subsets = [2, 2],
    pre = document.getElementById('out');

for (i = 0, l = factorial(array.length); i < l; i++) {
    pre.innerHTML += i.toString().padStart(4) +': ' + JSON.stringify(getN(i, array, subsets)) + '\n';
}

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

推荐答案

这是一个递归的公式，它将枚举实际元素的组合。在列表 [2,2] 中，每个 2 被视为不同的元素。我们可以输入任意模式，如 [1,2,3,4,5,6] 分为所有组合模式 [[x]，[ x，x]，[x，x，x]] 。

Here's a recursive formulation that will enumerate combinations of actual elements. In the list, [2,2], each 2 is considered a different element. We can enter arbitrary patterns like [1,2,3,4,5,6] divided into all combinations with pattern [[x],[x,x],[x,x,x]].

function f(ns, subs){
  if (ns.length != subs.reduce((a,b) => a+b))
    throw new Error('Subset cardinality mismatch');

  function g(i, _subs){
    if (i == ns.length)
      return [_subs];

    let res = [];
    const cardinalities = new Set();

    function h(j){
      let temp = _subs.map(x => x.slice());
      temp[j].push(ns[i]);
      res = res.concat(g(i + 1, temp));
    }

    for (let j=0; j<subs.length; j++){
      if (!_subs[j].length && !cardinalities.has(subs[j])){
        h(j);
        cardinalities.add(subs[j]);

      } else if (_subs[j].length && _subs[j].length < subs[j]){
        h(j);
      }
    }
    return res;
  }
  let _subs = [];
  subs.map(_ => _subs.push([]));

  return g(0, _subs);
}

console.log('\n[0,1,2,3], [2,2]:');
let str = '';
for (let i of f([0,1,2,3], [2,2]))
  str += '\n' + JSON.stringify(i);
console.log(str);

console.log('\n[0,1,2,3], [1,3]:');
str = '';
for (let i of f([0,1,2,3], [1,3]))
  str += '\n' + JSON.stringify(i);
console.log(str);

console.log('\n[0,1,2,3,4,5,6,7,8,9], [1,2,3,4]:');
str = '';
for (let i of f([0,1,2,3,4,5,6,7,8,9], [1,2,3,4]))
  str += '\n' + JSON.stringify(i);
console.log(str);

这篇关于将数组（元素组合）划分为自定义分区的所有方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！