2

介绍

在尝试对图中的节点进行一些分类（将呈现不同）时，我发现自己面临以下问题：

问题

给定一个元素的超集及其S = {0, 1, ... M}许多不相交的子集，其中，找出集合的划分的最佳算法是什么？nT_i0 <= i < nSP

P = S是原始超集的所有不相交分区的并集，其中，对于所有元素，每个“原始”集合中的“父”列表都相同。P_jS0 <= j < Mx in P_jxT_i

例子

S = [1, 2, 3, 4, 5, 6,   8, 9]

T_1 = [1, 4]
T_2 = [2, 3]
T_3 = [1, 3, 4]

所以所有P_j的 s 都是：

P_1 = [1, 4] # all elements x have the same list of "parents": T_1, T_3
P_2 = [2] # all elements x have the same list of "parents": T_2
P_3 = [3] # all elements x have the same list of "parents": T_2, T_3
P_4 = [5, 6, 8, 9] #  all elements x have the same list of "parents": S (so they're not in any of the P_j

问题

  1. python 包中有哪些好的函数/类来计算所有P_js及其“父母”列表，理想情况下仅限于numpyand scipy？也许已经有一个功能可以做到这一点
  2. 找到这些分区以及每个分区P_j的“父母”列表的最佳算法是什么？让我们注意T_0 = S

我认为蛮力方法是生成所有 2 个集合的组合T并将它们分成最多 3 个不相交的集合，这些集合将被添加回T集合池，然后重复该过程直到所有结果Ts 不相交，因此我们已经得到了我们的答案——P集合。一个小问题可能是在途中缓存所有“父母”。

我怀疑可以使用动态编程方法来优化算法。

注意：我很想用乳胶（通过MathJax）编写数学部分，但不幸的是这没有被激活:-(

4

2 回答 2

1

我这样做的方法是构造一个M × n布尔数组Inwhere . 您可以在 中构造它，前提是您可以通过扫描所有集合并在中标记相应位来将元素映射到其整数索引中。In(i, j) = Si ∈ TjO(Σj|Tj|)SO(1)TIn

然后，您可以通过将行连接成二进制位数来i直接读取每个元素的“签名” 。签名正是你正在寻找的分区的等价关系。Inin

顺便说一句，关于数学标记，我完全同意你的看法。也许是时候发起一场新的竞选活动了。

于 2012-12-22T23:08:30.657 回答
1

以下应该是线性时间（以 s 中的元素数量计T）。

from collections import defaultdict

S = [1, 2, 3, 4, 5, 6,   8, 9]

T_1 = [1, 4]
T_2 = [2, 3]
T_3 = [1, 3, 4]

Ts = [S, T_1, T_2, T_3]

parents = defaultdict(int)
for i, T in enumerate(Ts):
    for elem in T:
        parents[elem] += 2 ** i

children = defaultdict(list)
for elem, p in parents.items():
    children[p].append(elem)

print(list(children.values()))

结果：

[[5, 6, 8, 9], [1, 4], [2], [3]]
于 2012-12-22T23:01:12.497 回答