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

Question

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?

Answer 1

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

Answer 2

This generates all possible permutations of the wanted result, so it does not answer the question.

---

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

You could start with an array with combinations that contain only one element, then go over those combinations and merge two arrays of them, proceed recursively.

Playground

Answer 3

You could do it by enumerating all possible combinations, and then finding the permutatinos for every combination, and then filter the element to make sure they are unique. This filtering can be done by inserting into a Set.

The subset function is from @le_m (Check this answer).

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 4

You could first group same elements and count them, resulting in a table like this:

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

(1 is duplicated twice, 3 and 4 once)

Now you could start and take the first four elements out, then the 3 in the second row and then the one in the last row resulting in

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

Now to get the next combo, just take 3 out from the first row, and let the other values move up:

 1 |   | 3 | 4
 1 |   |    | 4

now again take out the rows, and you get

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

Now repeat this pattern with the first row (take 2, 1) and so on, also repeat that with the rows, then you should get the result you want to achieve.

 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 5

Implemented an algorithm from scratch that:

• gets the frequency of the letters,
• starts at the key length and works downwards towards 1
• while the frequency map is not empty
  • add the key to the sub-result

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