分區的超集，讓原來的集列表中的每個分區

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的「簽名」。簽名恰恰是您正在尋找的分區的等價關係。

順便說一句，我完全同意你關於數學標記。也許是時候開始一個新的活動。