球和籃筐版本2

Question

除了原來的球和籃子的問題，我這裏提到的：Balls and Baskets Problem Algorithm?

有一個稍微不同的問題。

還有N人，他們有無限的球，但他們這次沒有籃子。

問題是：

有N人無限球和M個不同的籃子。 人們把球扔到籃子裏。

我想找到正在向同一個籃子扔球的人羣。

人A拋出到籃1，2，4，，6,7，14，51，32 人員B拋出到籃3，4，6，7，14，15，16，64,43 人C投擲到籃筐3,4,6,7,5,87,42,32,52,55, 。 。 。 等

在這個例子中，人A和B可能連接良好（可以說朋友）（4,6,7,14常見） 和C也可以連接到它們，但連接不好。 （4,6,7共同）

我想找到一羣4-5人這樣的人在一個非常大的數據庫。

Answer 1

傑克遜的想法是一個開始。

當你找到了派系後，定義了共同購物籃爲每個派系，由所有egdes的籃子的交集。 （邊緣的籃子是這個邊緣節點代表的人們共有的籃子）。只有當公共籃子集大於X時，那麼這個集團代表一個真正連接的集團。

例如，在原有的問題，其邊緣將是：

A-B: weight=4, baskets=[4,6,7,14] 
A-C: weight=3, baskets=[4,6,7] 
B-C: weight=4, baskets=[3,4,6,7] 

如果修剪在小於3，則獲得，這是一個集團，用4,6-設定=共同籃子[， 7]。

在你給傑克遜答案的評論中給出的例子中，普通籃子集合是空的，所以你知道這些傢伙並沒有真正連接。

Answer 2

好吧，我最初的想法;將其作爲加權圖進行建模。讓人們成爲頂點，並在共享籃子時創建鏈接。如果他們共享多個籃子，則增加他們共享的每個籃子的鏈接權重。因此，在您的示例中，A和B之間的邊的權重爲4.

然後，您可以決定組中每個人的友好程度，修剪重量小於該值的邊，然後查找結果圖中的派系。