Select 来自一组子集的 n 项

Question

我想知道是否存在可以解决这个问题的算法：

假设你有一个包含集合的集合，其中每个集合可能有也可能没有元素，例如，让集合的可能元素为 1,2 和 3，那么我们将有一个集合像 {{1,2,3}{1}{1,2} ... } 所以，我如何 select 一些集合，这样我就有 n每个项目的元素，例如让n=200然后我想要200 1s，200 2s和200 3s 在这个例子中。

Answer 1

在我深入回答之前有一些疑问。

假设我们有一个方法 f() 给定一组集合（如您示例中的集合），它需要找到什么？

如果我们将 n = 3 插入到 f(3) 中，它需要找到这样的集合，使得每个项目都有 n 个元素（3 个 1、3 个 2 和 3 个 3）？让我们假设这个场景。

那么我们方法的输出应该是满足前面问题的集合的子集还是我们只需要return我们子集中的集合个数？例如一组集合中的f(3)如下

[[1,2,3][1][1,2][1,2][1,2,3][3]... ]

我们可以看到一个解决方案子集是[[1,2,3][1,2][1,2,3][3]] 我们可以 return 这个子集，或者说这个子集中的集合数，即 4。（这可能与算法的 space 复杂度有关）。

现在解决方案，朴素的方法可能是这种形式：

遍历一组集合。
对于单个集合中的每个元素，增加一个元素计数器（例如集合 [1,2] 将使 1 和 2 计数器各增加一个。
1. 如果其中一个元素数量大于 'n'，那么我们不会将该集合考虑到我们的解决方案中。
2. 否则，考虑将该集合纳入您的解决方案集合。
3. 无论如何，请再次调用您的方法，但不要考虑之前的设置。
4. return如果发现每个元素都增加了计数器等于'n'.

伪代码如下所示：

method find_sets(n,sets, sol_sets, element_counters):

    for each set in sets:
        updated_counter = element_counter +  1 for each element in set
        sets = sets.pop(set)

        if for a element in updated_counter > n:
            return method find_sets(n, sets, sol_sets, element_counters)

        else if for any element in updated_counter < n:
            sol_sets.add(set)
            return method find_sets(n, sets, sol_sets, updated_counter)

        else if for every element in updated_counter = n:
            sol_sets.add(set)
            return sol_sets

    # If the solution could not be found
     return None

考虑到一组 N 个集合，最坏的情况是对每个元素进行循环，考虑到这是一个递归算法，我们可以预期时间复杂度为 n²。

希望这能为找到更好的解决方案带来启示。

Select 来自一组子集的 n 项

Select n items from a set of subsets

python

algorithm

graph-algorithm

data-structures

python-3.x