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?

Epicene

This isn't a JS problem as much as a math problem. Give it a try, a first attempt attempt at least, and then we can help – Mathison

This might help you. – Grotto

I would say getting the set of distinct elements is a good first step; Now you need to get a count of how many times each of those elements appears in the original, then start populating arrays with those distinct elements. – Mazman

The third example combination is not unique. See Finding All Combinations of JavaScript array values – Lustig

Can you please clarify why [a,b,c] appears two times in your example of combinations. – Isoniazid

Sure, maybe I have misworded the question. What I want to achieve is, create subsets where each element is only repeated once. These subsets should add up to the full set. I have checked the links mentioned in the comments before, but they were different examples. – Epicene

Are [A, B, C] [A, B, C] [D, E] and [A, B, C] [D, E] [A, B, C] distinct combinations? How about [A, B, C] [A, B, C] [D, E] and [A, B, C] [C, A, B] [E, D]? Are singleton sets allowed (e.g., [A] [A] [B] [B] [C] [C] [D] [E])? – Viscous

Please clarify whether you require the last solution that @DavidEisenstat mentioned. If not, what are the criteria for eliminating some of those possibilities? I can see that it's not merely limited quantity of covering sets, as your given examples include 3 sets when a minimum of 2 is possible. – Disrepute

The answer @Mr. Polywhirl produces the desired result. So, the combinations that DavidEisenstat mentioned are not distinct combinations. – Epicene

[A,B] [A,B,C] [C,D,E] seems a perfectly legitimate combination according to your question, but it is not produced by the solution of @Mr. Polywhirl. If it is legitimate, the answer of @Mr. Polywhirl is wrong. If it is not, you should explain why, and edit your question. – Krenek

I have no idea why you think Mr. Polywhirl's answer produces what you seem to be asking for. Can you please explain? (If I'm following correctly, my answer seems to show 315 different ways to partition the multiset with each part having distinct elements.) – Pantelleria

Hey, @גלעדברקן so I've taken a look again and in fact the 315 possibilities seem to be the right answer. I have tried out Mr. Poltwhirl's algorithm in my code and for my purposes it serves well because when the combinations become like [AB] [A] [B] [C]... and so on, it doesn't produce the desired result, so I can safely ignore those possiblities. The broader context is not necessary to explain right now I think, but for what I asked above, your answer is the most precise one right now :) – Epicene

to recap: 315 possibilities is the right answer, except that, for your application, you would discard those that contain sets of a single element, like [A], even if there is only one of them, which leaves us with 37 possibilities. Did I get it correctly? – Krenek

@WalterTross Yes. I'm trying to optimize something, and the best outcome comes from distinct and grouped up elements. So in our example, our array has 8 elements, and the most optimal groups could be 5-3 or 4-4 or 3-3-2 and so on. The only part I had the problem was dividing the array into the groups, so that's why I have only written about that part and not the whole problem. But from what I learned since yesterday, I will try to be a lot clearer the next time I ask something, sorry for the confusions. – Epicene

@WalterTross I have one for custom partitions, too :) But it doesn't maintain parts with distinct elements. I guess the next thing might be to combine the two. – Pantelleria

@Epicene I took the liberty of editing the title of the question to be more descriptive. I hope that's ok. You're free to change it, of course. (And to ask another, perhaps, about custom (rather than all) partitions where each part has distinct elements :) – Pantelleria

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

Student

So from what I understood, the show method is just there to output the array. Is it possible to output all the combinations in a two dimensional array, where each row is one combination of subsets from the original array? – Epicene

@Epicene the function f is the one returning the solution. Each element in any one result is in a form, ["set", N], which tells us there are N instances of the set set in this combination (i.e., ["ABD", 2] would mean [A,B,D], [A,B,D]). Can you make a function to convert the result to the form you want, expanding out the set (hint: JavaScript String split method) and duplicating it N times? (if not, I can add it a little later.) – Pantelleria

@Epicene I've added a function called allPartitions that does the conversion, at the following link: repl.it/@gl_dbrqn/IllegalComposedBracket Hope that helps! – Pantelleria

Thank you! It works nearly perfectly now! I just have one question though, I'm trying to make it such that instead of having [ [ 'A', 'AB', 'BC' ], [ 'A', 'ABC', 'B' ], I want to have it as [ [ 'A', ['A', 'B'], ['B', 'C'] ], [ 'A', ['A', 'B', 'C'], 'B' ] so that when I use not letters but arbitrary strings as the elements of the input array, I would still be able to see them and count them. How can I achieve this? – Epicene

@Epicene I'm not sure what you mean. Can you please provide one clear example of your desired input and desired output? – Pantelleria

Sure, for example when I input this [["apple", 1], ["orange", 2]] the output is: [ [ [ 'A', 'p', 'p', 'l', 'e', 'O', 'r', 'a', 'n', 'g', 'e' ], [ 'O', 'r', 'a', 'n', 'g', 'e' ] ], [ [ 'A', 'p', 'p', 'l', 'e' ], [ 'O', 'r', 'a', 'n', 'g', 'e' ], [ 'O', 'r', 'a', 'n', 'g', 'e' ] ] ] But the desired output would be ```[ [ [Apple, Orange], [Orange] ], [ [Apple] , [Orange] , [Orange] ] ] – Epicene

@Epicene ah, I see what you mean, the current code assumes the elements of the input are single character strings. I am away from a computer right now but I will make a change later to accept more general input. – Pantelleria

@Epicene as an aside, I think your request is more of a coding request than an algorithm request. I think it would be reasonable to ask you to find a way to utilize the current implementation -- for example, with a little JavaScript skill, you could make a map that mapped "A" to "Apple" and "B" to "Orange", then run the current implementation and map the results back to whatever you want (in this case "Apple"s and "Orange"s). This kind of challenge would be a good and I hope not too difficult learning experience for you. What do you think? – Pantelleria

Sure, I will try that right away and let's see how it goes, thanks for all the help! – Epicene

@Epicene no problem, thanks for an interesting question. (By the way, out of laziness, the way I would probably implement accepting the more general input would be by using a similar kind of map :) – Pantelleria

@Epicene I added the mapping idea to the allPartitions function here: repl.it/@gl_dbrqn/IllegalComposedBracket passing longer strings or just arbitrary elements should work now (see the example at the end). Please let me know if you find any issues. – Pantelleria

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

Gina

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

Applesauce

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

Gina

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

Homesick

Seems to be missing quite a few. Here's one: A | A | B | B | C | C | D | E – Pantelleria

@גלעדברקן That is because I stopped short... max > 1 instead of max > 0. Did not think the single elements were wanted. – Homesick

even with this replacement lots are still missing, e.g. AB | AB | CD | C | E – Krenek

@WalterTross I tried your algorithm with a case of 23 elements, and below is the output: ABCDE | ABCDE | ABCDE | ABCDE | ABD ABCD | ABCD | ABCD | ABCD | ABDE | E | E | E ABC | ABC | ABC | ABC | ABD | DE | DE | DE | DE AB | AB | AB | AB | AB | CD | CD | CD | CD | DE | E | E | E A | A | A | A | A | B | B | B | B | B | C | C | C | C | D | D | D | D | D | E | E | E | E but I've noticed that one important result is skipped. Between the 1st and the 2nd lines, there should be a line such as ABCDE | ABCDE | ABCDE | ABCD | ABDE Do you know why this could be happening? – Epicene

@Epicene I wrote no algorithm, maybe you were addressing Mr. Polywhirl. Your comment is not clear at all though, and anyway, Mr. Polywhirl's algorithm, as it is now, when run on your question's data, outputs 4 lines when there should be 37 or 315, depending on the interpretation. – Krenek

Yes, sorry I meant @Mr.Polywhirl – Epicene