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

  • A+
Category:Languages

Let's say we have such an array: myArray = [A, A, B, B, C, C, D, E]

I would like to create an algorithm so that it will find all the combinations that add up to the whole array, where none of the elements are repeated.

Example combinations:

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

Clarification: [A, B, C] [A, B, C] [D, E] and [A, B, C] [D, E] [A, B, C] are the same combinations. Also the ordering with the subsets doesn't matter as well. For example [A,B,C] and [B,A,C] should be the same. So far, I didn't progress beyond

var myArray = ["A", "A", "B", "B", "C", "C", "D", "E"]  console.log([...new Set(myArray)])

But this doesn't help at all, it just returns one distinct set. I couldn't find a similar problem posted before, so could anyone guide me here in how to achieve this?

 


I'm getting 315 combinations. Is that right? :)

Here's a recursion:

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

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: