球和篮筐版本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.

然后，您可以决定组中每个人的友好程度，修剪重量小于该值的边，然后查找结果图中的派系。