分区的超集，让原来的集列表中的每个分区

Question

介绍

在试图做一个曲线图上节点的一些cathegorization（将呈现differenty），我发现自己面临着以下问题：

的问题

鉴于元件S = {0, 1, ... M}超集和非不相交子集其T_i若干n，与0 <= i < n，什么是最好的ALG算法找出该集合的分区S，称为P？

P = S是所有脱节分区原超S的P_j的工会，与0 <= j < M，使得对所有的元素x in P_j，每x有“父母”的同一列表中的“原始”设置T_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_j小号和他们的“父母”，理想的名单限制为numpy和scipy？也许已经有这样一个功能
2. 什么是最好的算法找到这些分区P_j s 和为每一个，“父母”的列表？让我们注意T_0 = S

我觉得蛮力的方法是产生T将所有2组合和拆分它们在至多3个不相交的集合，这将被添加回T集和池然后重复这个过程直到所有产生的T不相交，因此我们已经到达了我们的答案 - P集合。有一点问题可能是在那里缓存所有的“父母”。

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

注：我会爱到写在乳胶（通过MathJax）数学部分，但不幸的是这不是:-(

Answer 1

激活以下应该是线性的时间（以数量在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]] 

Answer 2

我会做到这一点的方法是构建一个M × n布尔数组In其中In(i, j) = Si ∈ Tj。只要扫描所有集合T并标记In中的相应位，即可将S的元素映射到其整数索引O(1)中，您可以在O(Σj|Tj|)中构建该元素。

然后可以通过连接行i成n比特的二进制数读出的直接从In每个元素i的“签名”。签名恰恰是您正在寻找的分区的等价关系。

顺便说一句，我完全同意你关于数学标记。也许是时候开始一个新的活动。