算法：找出哪些对象包含输入数组的子集

Question

我们有一些对象（大约100,000个对象），每个对象有一个属性和一些整数（范围从1到20,000，最多20个元素，没有重复的元素。）：

例如：

object_1: [1, 4]
object_2: [1, 3]
object_3: [100]

问题是，我们输入一个整数数组（称为A），找出哪些对象包含A的子集。

例如：

当A = [1]时，输出应该是[]
当A = [1, 4]时，输出应该是[object_1]
当A = [1, 3, 4]时，输出应该是[object_1, object_2]

问题描述在python:

from typing import List


# problem description

class Object(object):

    def __init__(self, integers):
        self.integers = integers

    def size(self):
        return len(self.integers)


object_1 = Object([1, 4])
object_2 = Object([1, 3])
object_3 = Object([100])


def _find_subset_objects(integers):  # type: (List[int]) -> List[Object]
    raise NotImplementedError()


def test(find_subset_objects=_find_subset_objects):
    assert find_subset_objects([1]) == []
    assert find_subset_objects([1, 4]) == [object_1]
    assert find_subset_objects([1, 3, 4]) == [object_1, object_2]

是否有一些算法或一些数据结构旨在解决此类问题？

Answer 1

将对象存储在数组中。索引将为 0 ... ~100K。然后创建两个辅助数组。

第一个包含每个对象的元素计数。我将调用此数组 obj_total（如果您愿意，可以通过调用 object.size 或类似的名称来省略。）
第二个用零初始化。我将其命名为 current_object_count.

对于每个整数属性 p 其中 0 < p <= 20000，创建一个索引列表，其中索引 [列表中的=24=]i表示该元素包含在第i个对象中。

越来越乱了，我在名字中迷路了。使用您在问题中使用的对象的示例时间：

objects = [[1, 4], [1, 3], [100]]
obj_total = [2, 2, 1]
current_object_count = [0, 0, 0]
object_1_ref = [0, 1]
object_2_ref = [ ]
object_3_ref = [1]
object_4_ref = [0]
object_100_ref = [100]
object_refs = [object_1_ref ,object_2_ref , ... , object_100_ref]
#Note that you will want to do this references dynamically.
#I'm writing them out only for the sake of clarity.

现在我们得到了输入数组，例如 [1, 3, 4]。对于数组中的每个元素 i，我们查看 object_i_ref。然后我们使用参考数组中的索引来增加 current_object_count 数组中的值。
每当您增加 current_object_count[x] 中的值时，您也会检查 obj_total[x] 数组。如果值匹配，则 objects[x] 中的对象是输入数组的子集，我们可以记下它。

完成输入数组后，您将获得所有结果。

算法：找出哪些对象包含输入数组的子集

Algorithm: Find out which objects hold the subset of input array

algorithm

union

set

subset