英文:
Is there a data structure that allows you to return all the sets that contain this element?
问题
我正在寻找一种数据结构，它能够返回包含特定元素的所有集合，同时支持集合的添加和删除操作。
显而易见的方法是将每个集合存储为哈希表，并在每次查询时检查集合是否包含给定元素。
但存在一些限制：
- 给定的集合可以相互交叉或甚至包含在彼此内。
- 保证元素的数量远大于集合的数量。
- 需要支持更新和删除集合的操作。
更具体地说，
给定一些集合 S_1, S_2, S_3, ... S_n。每个集合由其元素的枚举定义。
我需要一种数据结构，允许我有效地执行以下操作：
get(E) - 获取包含给定元素 E 的所有集合
add(i, S) - 添加第 i 个集合
update(i, S) - 更新第 i 个集合
delete(i) - 删除第 i 个集合
英文:
I am looking for a data structure that returns all sets that contain a given element, as well as supporting set addition and deletion operations
The obvious approach is to store each set as a hash table and for each query check whether the sets contain a given element
But there are some limitations
- The given sets can intersect each other or even contain
- It is guaranteed that the number of elements is much larger than the number of sets
- It is necessary to support the operation of updating and deleting sets
More stricly
Given a number of sets S_1, S_2, S_3, ... S_n. Each set is defined by an enumeration of its elements <br>
I need a data structure that will allow me to effectively perform the following operations: <br>
get(E) - Get all sets that contain a given element E <br>
add(i, S) - Add the i-th set <br>
update(i, S) - Update the i-th set <br>
delete(i) - Delete the i-th set
答案1
得分: 0
你要找的数据结构是一个(稀疏)二分(无向)图。
在这里，对于每个元素 e 和每个集合 S，你会有一个额外的顶点。对于每个 e 在 S 中，你会有一条边 {e,S} 在 E 中。然后，检查集合 S 简化为：给我 S 的邻居。检查所有包含 e 的集合简化为：给我 e 的邻居。向集合添加值意味着插入新边，删除元素意味着删除边。你可能还想确保完全删除孤立的顶点。
英文:
The data structure you are looking for is a (sparse) bipartite (undirected) graph.
Here, for each element e and each set S you would have an extra vertex. And for each e in S you would have an edge {e,S} in E. Then, examining set S boils down to: give me S's neighbours. Examining all sets e belongs to boils down to: give me e's neighbours. Adding values to sets means inserting new edges, and removing elements means removing edges. You might also want to make sure to entirely remove isolated vertices.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论