这个集合内容比较有通用的算法吗？这个叫什么？
Is there a common algorithm for this set content comparison? What is this called?
我正在 python 编码。
我有一个集合列表。这些集合包含整数。如果两个集合共享一个整数项，则为 "connected"。我的目标是确定所有这些集合是否都相互连接成一个组（而不是没有连接的集合或多组相互连接的集合）。
有通用的算法吗？这似乎是一个广泛适用的目标。
这是我提出的解决方案：
从第一个集合开始，检查内容是否与任何其他集合共享
删除任何包含共享内容的集合并将其他内容添加到第一个集合
重复直到第一组没有变化
如果所有其他集合都已删除，则它们都已连接
澄清
我想区分一个相互连接的集合链
o--o--o--o--o--o
来自相互连接的不同组
o--o--o o--o--o
所以，仅仅检查每个集合是否连接到另一个集合是不够的。
以下是我会尝试的方法：
- 检查每组对。
比较每个集合成员：
如果有一个共同的 Integer 则留下一组并继续另一组，继续此操作直到没有更多组。
如果没有任何成员共享则中断并输出 false。
您的解决方案是正确的，并且是 DFS 的一个变体（尽管由于您操纵集合，它可能效率有点低）
你的问题基本上是一个图形问题，其中 graph 是：
G = (V,E)
V = { sets } = {S1, S2, ..., Sn}
E = { (Si,Sj) | Si and Sj share an integer }
这个图本质上是无向的，你的问题是判断它是否连通。这可以通过 BFS or DFS 来完成。只需从一个任意顶点开始，直到 "stuck"（无需从新源重新启动）。如果发生这种情况时，您有 "discovered" 个所有集合，则该图已连接。否则不是。
运行时间是O(|V|+|E|)，其中|V|是你的套数，|E|是连接数。
注：集合E可以通过创建一个inverted index来有效地计算稀疏图。对于每个数字，创建包含该数字的所有集合的列表（这是输入大小的线性），然后通过遍历列表中的所有对生成边（对于稀疏图，这应该相当小） .
尽管对于密集图，生成它的更有效方法可能只是遍历所有对集。
如果已知可能的整数并且它们的数量有一个小的上限，如 32，您可以将每个集合表示为位向量并按位应用 和 ，如下所示：x(n) = x(n-1) & s(n) 其中 s(n) 是第 n 个集合，& 是按位 和 。如果 x(n) 的所有位对于任何 n 都为零，您将知道存在多组集合。这种方法的时间复杂度是线性的，并且使用当前硬件可以非常有效地执行的操作。
可以通过以下检查扩展此解决方案和任何其他解决方案。它必须在原始解决方案之前应用。这个想法是在某些情况下快速完成。检查要求知道每个集合的最小和最大整数。如果所有这些最小整数中的最大整数大于所有最大整数中的最小整数，您就会知道存在多组集合。所以，在这种情况下你可以完成。如果条件不成立，您将不得不继续原来的解决方案。
我正在 python 编码。
我有一个集合列表。这些集合包含整数。如果两个集合共享一个整数项，则为 "connected"。我的目标是确定所有这些集合是否都相互连接成一个组（而不是没有连接的集合或多组相互连接的集合）。
有通用的算法吗？这似乎是一个广泛适用的目标。
这是我提出的解决方案：
从第一个集合开始，检查内容是否与任何其他集合共享
删除任何包含共享内容的集合并将其他内容添加到第一个集合
重复直到第一组没有变化
如果所有其他集合都已删除，则它们都已连接
澄清
我想区分一个相互连接的集合链
o--o--o--o--o--o
来自相互连接的不同组
o--o--o o--o--o
所以，仅仅检查每个集合是否连接到另一个集合是不够的。
以下是我会尝试的方法：
- 检查每组对。
比较每个集合成员：
如果有一个共同的 Integer 则留下一组并继续另一组，继续此操作直到没有更多组。
如果没有任何成员共享则中断并输出 false。
您的解决方案是正确的，并且是 DFS 的一个变体（尽管由于您操纵集合，它可能效率有点低）
你的问题基本上是一个图形问题，其中 graph 是：
G = (V,E)
V = { sets } = {S1, S2, ..., Sn}
E = { (Si,Sj) | Si and Sj share an integer }
这个图本质上是无向的，你的问题是判断它是否连通。这可以通过 BFS or DFS 来完成。只需从一个任意顶点开始，直到 "stuck"（无需从新源重新启动）。如果发生这种情况时，您有 "discovered" 个所有集合，则该图已连接。否则不是。
运行时间是O(|V|+|E|)，其中|V|是你的套数，|E|是连接数。
注：集合E可以通过创建一个inverted index来有效地计算稀疏图。对于每个数字，创建包含该数字的所有集合的列表（这是输入大小的线性），然后通过遍历列表中的所有对生成边（对于稀疏图，这应该相当小） .
尽管对于密集图，生成它的更有效方法可能只是遍历所有对集。
如果已知可能的整数并且它们的数量有一个小的上限，如 32，您可以将每个集合表示为位向量并按位应用 和 ，如下所示：x(n) = x(n-1) & s(n) 其中 s(n) 是第 n 个集合，& 是按位 和 。如果 x(n) 的所有位对于任何 n 都为零，您将知道存在多组集合。这种方法的时间复杂度是线性的，并且使用当前硬件可以非常有效地执行的操作。
可以通过以下检查扩展此解决方案和任何其他解决方案。它必须在原始解决方案之前应用。这个想法是在某些情况下快速完成。检查要求知道每个集合的最小和最大整数。如果所有这些最小整数中的最大整数大于所有最大整数中的最小整数，您就会知道存在多组集合。所以，在这种情况下你可以完成。如果条件不成立，您将不得不继续原来的解决方案。