All ways of dividing an array (element combinations) into a custom partition

Question

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>

An easy (but not optimized) solution would be to remove permutations from the result array. — Kresimir, Dec 07 '18 at 09:22
Yes I know, but i'm looking for fast optimized solution, not generating permutations. — J.Doe, Dec 07 '18 at 09:41
What I means is how large the size of the array should be? and the size pattern? — Pham Trung, Dec 07 '18 at 09:58
With array size `n`, and the pattern size `m`, the number of valid answer will be `n!/(m! ^ (n/m))` , which for example, if `n = 20, and m = 2 -> 20! / 2^10` which is still very large. — Pham Trung, Dec 07 '18 at 10:04
I've edited the question. Array size 1 < n < 100. Size of pattern will fit the size of array. I know it is still very large. But smaller than with permutations. — J.Doe, Dec 07 '18 at 10:06
Not worth the effort honestly, for n = 100, and m = 100, yeah, there is only one, but a slightly smaller group m = 50 , there are already 1.0089134e+29 unique answers; m = 25, there are 1.6122075e+57 unique answers. — Pham Trung, Dec 07 '18 at 10:10
Possible duplicate of [Permutations - all possible sets of numbers](https://stackoverflow.com/questions/5506888/permutations-all-possible-sets-of-numbers) — Tigger, Dec 07 '18 at 11:12
No, it's not duplicate. It's the opposite of this question. I need to get rid off permutations, not make them. — J.Doe, Dec 07 '18 at 11:16
@PhamTrung what's more interesting is a division into multiple `m`s. Like [0..9] divided into [[x],[x,x],[x,x,x],[x,x,x,x]]. https://repl.it/@gl_dbrqn/OnerlookedCulturedComputergames — גלעד ברקן, Dec 08 '18 at 16:01

גלעד ברקן · Accepted Answer · 2018-12-08T17:05:03.587

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

Nice solution, I think this is a challenging implementation, so glad to see you have nicely put it :). — Pham Trung, Dec 10 '18 at 09:23

score 0 · Answer 2 · answered Dec 08 '18 at 18:13

0

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

answered Dec 08 '18 at 18:13

Redu

25,060
6
56
76

Unlike my answer, this doesn't allow for arbitrary patterns like [1,2,3,4,5,6] divided into combinations with pattern [[x],[x,x],[x,x,x]]. – גלעד ברקן Dec 08 '18 at 18:18
Come to think of it, I'm not sure if this actually answers the question at all. – גלעד ברקן Dec 08 '18 at 18:21

All ways of dividing an array (element combinations) into a custom partition

2 Answers2

Linked