All ways of dividing an array (element combination

问题:

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

For instance:

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

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

Expected result:

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

or

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

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>

回答1:

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);

回答2:

I guess you want n combinations of an array. You may do as follows;

Array.prototype.combinations = function(n){
  return this.reduce((p,c,i,a) => p.concat(n > 1 ? a.slice(i+1).combinations(n-1).map(e => [].concat(e,c))
                                                 : [[c]]),[]);
};

var result = [1,2,3,4].combinations(2);
console.log(JSON.stringify(result));
    result = [1,2,3,4,5,6].combinations(3);
console.log(JSON.stringify(result));