从一组子集中选择n个项目

Question

我想知道是否有一种算法可以解决这个问题：

假设你有一个集合，里面有集合，其中每个集合可能有元素，也可能没有元素，例如，让集合的可能元素是1,2和3，那么我们就有一个像{{1,2,3}{1}{1,2}…}这样的集合那么，我如何选择多个集合，使每个项目都有n元素，例如，如果n=200，那么在本例中，我想要2001s、2002s和2003s

Answer 1

在我深入研究答案之前，有一些疑问句。

假设我们有一个方法f((，它给出了一组集合(就像您的例子中的那个(，它需要找到什么？

如果我们把n=3代入f(3(，它需要找到集合，这样我们每个项目都有n个元素(3个1，3个2，和3个3(？让我们假设这种情况。

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

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

我们可以看到一个解子集是[[1,2,3][1,2][1,2,3][3]]我们可以返回这个子集，或者更确切地说，返回这个子集中的集合数，即4。(这可能与算法的空间复杂性有关(。

现在的解决方案是，一种天真的方法可以是这样的形式：

1. 循环遍历集合集
2. 对于单个集合中的每个元素，增加一个元素计数器(例如，集合[1，2]将使1和2计数器各增加一个。
   1. 如果其中一个元素计数大于'n'，则我们不在解决方案中考虑该集合
   2. 否则，将该集合考虑到您的解决方案集中
   3. 不管是什么情况，请再次调用您的方法，但不要考虑前一个集合
   4. 如果您发现每个元素都增加了等于'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²。

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