在Python中查找n個最大的集合集合

我有一組字符集合（字典），比如{1: {'a', 'b'}, ...}我需要找到n個最大的交集，即集合的最大子集的交集。明顯的蠻力方法：在Python中查找n個最大的集合集合

for i in range(len(collection),2,-1): 
    for subset in combinations(sorted(collection), i): 
     intersected = set.intersection(*(collection[k] for k in subset)) 
     if len(intersected)>0: 
      yield len(subset), intersected

是非常緩慢的。有沒有一些有效的方法/庫來做到這一點？

來源

2015-12-20 david brick

它適用於我的數據集，雖然速度很慢。作爲澄清，最大的我是指集合中最大的子集（最大數量的重疊子集），不一定是元素數量最大的交集。 –

你是什麼意思「n最大的十字路口」？什麼是「n」？你認爲這些藏品的最大子集的交集是什麼？ –

一些最小的示例輸入和輸出數據將會有所幫助。 –

只計算每個字符串的發生次數。 occurances的最大數量爲子集的最大交集（假設一個字符串中的每個子集是唯一的）：

coll = {1:{'a','b'}, 2:{'b','e'}, 3:{'a','c'}, 4:{'b','f'}} 
print(coll) 

d=dict() 
for subs in coll.values(): 
    for s in subs: 
    d[s]=d.setdefault(s, 0)+1 

m=max(d.values()) 
print(m)

來源

2015-12-20 14:28:32

我假設你想找到你的字典中對應的集合的交集不爲空的n個最大子集。因此，就像在你的例子中那樣，最大的這樣的子集由關鍵字1,2和4表示，並且相應集合的交集至少包含一個元素（在我們的例子中爲'b'）。

最大子集： 代替生成密鑰的所有可能的子集，則可以僅僅遍歷所有不同組元素（A，B等），並計算出它們發生集的數目。具有最高計數的元素將直接導向解決方案，即最大的子集。

實施例：在您的例子你會得到以下的中間結果：

一個：2， B：3， C：1， E：1， F：1

您立即看到元素b比其他元素多出現在集合中。包含b的集合表示解決方案。

N個最大的子集： n個最大的子集可以很容易地從中間結果生成，你只需要檢查重複。在你的例子中，最大的子集的大小爲3，是其大小中的唯一一個。下一個最大的子集的大小爲2.您可以通過出現在兩個或更多集合中的元素（即a和b）獲得它。所以有三種方法可以從3個B組中挑選2個，並且可以從兩個A組中選擇一個解決方案。

來源

2015-12-20 14:14:04 lex82

不確定這是否正確。取集：{a，b，c} {a，b，c} {d，e} {d，f}，{d，g}。 d出現頻率最高，但最大的交叉點與{a，b，c}相交{a，b，c}。 – nickdu

問題是，這個問題被誤導了。真正要求的是如何找到一組選擇，以便在最大化選擇的大小時使它們的交集不爲空（請參閱問題下方的註釋）。 – lex82

在Python中查找n個最大的集合集合

回答

相關問題