algorithm - 查找由单个 MultiSet 中的元素组成的一组 MultiSet 的所有子集（无需替换）

Question

同一作者¹最近 提出的两个问题通常用相同的技术解决。在我看来，这将是一个经过研究并且可能很好解决的问题。

我想知道它可能被称为什么以及在哪里可以找到有关它的更多信息，假设这是一个众所周知的问题

这是我自己对这个问题的表述：

如果我们有一个 Set, M, 的 MultiSets ² , M_1-M_n由 Set 的元素组成S, 我们有一个 MultiSet 的组件, C, 也来自S, 我们如何找到M这样的所有子集, 对于每个子集, 每个子集的多重性其并集中的元素S不大于C?中该元素的多重性。³

例如，解释我自己对第一个问题的回答：

我想我明白你想要的是这样的：

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

simultaneousItems (catalog, components) 

屈服

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

结果中的每个数组都是目录项的子集，可以用提供的组件一起制作。因此，例如，没有一个输出数组包含"adf"or "def"，因为我们"f"在组件中没有，并且它们都没有同时包含， "ad"因为我们在组件列表中"aab"只有两个s。"a"

请注意，我使用"abc"的是包含字符串"a"、"b"和的集合的简写"c"。

最初的问题似乎是在寻找最大子集，所以还有一个额外的步骤，这可能是一个同样有趣的问题，但我对上面的版本更好奇。

请不要将我的解决方案视为任何一种算法理想。这是第一个想到的想法。

这是一个众所周知的问题吗？与背包问题和其他包装问题有一些模糊的关系，但我不太清楚要搜索什么以及在哪里搜索。

---

¹第一个更接近我认为的基本算法问题。我假设第二个更接近 OP 试图解决的真正问题。在没有来自 OP 的任何反馈的情况下，我不确定我的答案是否符合真正的需求，但无论如何我觉得这是一个有趣的问题。

²或Bag或mset。（定义）

^3如果C = { S_1^m(z_1) , S_2^m(z_2) , ... S_j^m(z_j) } 对于某个整数j ，更明确（请原谅我离正式的数学课太远） ，和S_1 , S_2 , ... S_j在S中，如果N = { M_a_1 , M_a_2 , ... M_a_k } 是结果中M的子集之一，并且 ∪ { M_a_1 , M_a_2 , ... M_a_k } = { S_1^m(x_1) , S_2^m(x_2) , ...S_j^m(x_j) }，那么对于所有i，x_i ≤ z_i。

标签： algorithmcomputer-science