1

Two recent questions by the same author 1 are generally solved by the same technique. This feels to me like it would be a studied and perhaps well solved problem.

I would like to know what it might be called and where to find more information about it, assuming it is a well-known problem

This is my own phrasing of the question:

If we have a Set, M, of MultiSets2, M_1 - M_n made up of elements of Set S, and we have a MultiSet of components, C, also drawn from S, how do we find all subsets of M such that the for each subset, the multiplicities of each element of S in its union is no greater than the multiplicity of that element in C?3

For example, paraphrasing my own answer to the first question:

I think I understand that what you want would be for something like this:

const catalog= ["ad", "aab", "ace", "cd", "ba", "bd", "adf", "def"]
const components = ["a", "b", "a", "c", "d", "e"]

simultaneousItems (catalog, components)

to yield

[
  ["ad", "ace"], ["ad", "ba"], ["ad"], ["aab", "cd"], ["aab"], ["ace", "ba"], 
  ["ace", "bd"], ["ace"],["cd", "ba"], ["cd"], ["ba"], ["bd"], []
]

where every array in the result is subset of catalog items that can be made together out of the components supplied. So, for instance, none of the output arrays contains "adf" or "def", since we have no "f" in the components, and none of them contain both "ad" and "aab" since we only have two "a"s in the component list.

Note that I'm using "abc" as a shorthand for the set containing the strings "a", "b", and "c".

The original problems seemed to be looking for maximal subsets, so there is one additional step, and that is perhaps an equally interesting problem, but I'm more curious about the version above.

Please don't look at my solution as any sort of algorithmic ideal. It was the first idea that came to mind.

Is this a well-known problem? There's some vague relationship to the Knapsack problem, and other packing problems, but I can't quite figure out what and where to search.

1 The first one is closer to what I think is the fundamental algorithmic question. I'm assuming the second one is closer to the real problem the OP is trying to solve. Without any feedback yet from the OP, I don't know for certain that my answers match the real need, but I find this an interesting question regardless.

2 Or Bag or mset. (definition)

3 More explicitly (and forgive me for being too far away from formal Math classes) if C = {S_1^m(z_1), S_2^m(z_2), ... S_j^m(z_j)} for some integer j, and S_1, S_2, ... S_j in S, and if N = {M_a_1, M_a_2, ... M_a_k} is one of the subset of M in the result, and ∪ {M_a_1, M_a_2, ... M_a_k} = {S_1^m(x_1), S_2^m(x_2), ... S_j^m(x_j)}, then for all i, x_i ≤ z_i.

Scott Sauyet
  • 49,207
  • 4
  • 49
  • 103
  • I love this problem. I can't say I've seen one exactly like it before. My brain first reached for sets too, but JS sets are so weak. For example, `const x = new Set([1]); const y = new Set([1]); const z = new Set(x); z.has(y)` returns `false`. A better set data structure would go a long way in solving this problem. Going to have to study this some more .... – Mulan Dec 23 '20 at 15:38
  • And JS certainly has nothing like MultiSets, although it would be easy enough to implement one. As you point out, though, JS Sets use reference equality, meaning they're not much help for anything beyond primitives. Ramda has an internal _Set type using value equality, but it's fairly inefficient and not publicly exposed. I wonder if some HashSet implementation would be worth pursuing. (Perhaps a simpler example of the issue would be `const x = new Set([{a: 1}]); x.has({a: 1}) //=> false`.) – Scott Sauyet Dec 23 '20 at 15:53
  • I would suggest asking on https://cs.stackexchange.com/. Personally I look at this and immediately know a way to do it, which is good enough for me. – btilly Dec 23 '20 at 16:56
  • @btilly: thanks. I don't spend much time there, so I don't know its conventions, but that probably makes sense. Yes, I only asked here after I had a solution. I'm just curious about whether this is an already-researched problem. – Scott Sauyet Dec 23 '20 at 17:04
  • Opened on the cs site: https://cs.stackexchange.com/q/133611/120212 – Scott Sauyet Dec 23 '20 at 20:20

0 Answers0