从整数集合列表中选择整数集合的Need算法

Question

我有一个列表，它的成员是从1到600或0到599中选择的5个数字的集合，用于存储。我需要选择这个列表的一个子列表，以便在这个子列表中的集合中，1到600范围内的每个整数恰好出现一次，所以一个包含120个元素的子列表。我的列表中有4200或840个元素--我将通过运行更大的数字来确定是否需要更大的元素。我需要任何一个这样的子列表。

这对我来说听起来像是一个标准问题，但我不知道如何搜索。有人能帮我提供一个算法吗？

Answer 1

来自Set Cover Problem

贪婪的集合覆盖算法根据一条规则选择集合:在每个阶段，选择包含最多未覆盖元素的集合

维基百科似乎说，这个算法在合理的复杂性假设下工作得最好。

我会将其归结为以下步骤：

1. 从列表中选择一个元素(可能是第一个)
2. 选择您遇到的下一个元素，其中所有5个数字都未在子列表中表示
3. 如果到达末尾，请返回到列表的开头，并降低第2步到第4步的条件第2步和第3步，直到您覆盖了所有整数

根据您正在使用的编程语言，有一些方法可以使这一过程变得非常迅速。

编辑:发帖者已经解释了每个整数必须精确地使用

所以，你真正需要做的就是继续添加元素，直到元素包含一个已经存在于你的子集中的整数。“确切”标准优先于“还不在子集中”标准。当你达到120个子集时，你就会跳出这个循环。

您可能还希望跟踪向子集添加元素的顺序，当遇到死胡同时(例如，超集中剩余的每个元素都包含一个已经存在于子集中的整数)，您可以回溯一个元素并继续。

为了回溯和记住哪些组合不起作用，你需要保留一个“禁用集合”的列表，每次你决定是否添加一个新元素时，你应该首先确保它不在这个禁用集合列表中。在Ruby中，最好的方法(据我所知)是存储集合的Hash，而不是存储集合本身。这提供了一种廉价的方法来评估预期的集合是否已经尝试过，并导致了死胡同。

祝好运!