공 및 바구니 VER2는

Question

원래 공 및 바구니 문제뿐만 아니라 내가 여기에 언급 : Balls and Baskets Problem Algorithm?

약간 다른 문제가 있습니다.

아직 N 명의 사람들이 있으며 무제한 볼을 가지고 있지만 이번에는 바구니가 없습니다.

문제는 다음과 같습니다 무제한 공 및 M 다른 바구니와 N 사람들이 있습니다

. 사람들은 바구니에 공을 던집니다.

같은 바구니에 공을 던지는 사람들의 그룹을 찾고 싶습니다.

인 바구니 A는 1, 2, 4, 6, 7, 14, 51 슬로우 32 인 B는 64,43 인 바구니 3, 4, 6, 7, 14, 15, 16 슬로우 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가됩니다.

그런 다음 그룹의 모든 사람들이 그 값보다 작은 가중치를 갖는 가장자리를 잘라 내고 찾아야 할 것을 결정할 수 있습니다. 파벌을 결과 그래프에 표시합니다.