공과 바구니 Ver2

Question

원래 공과 바구니 문제 외에도 여기에 언급했습니다. 공과 바구니 문제 알고리즘?

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

여전히 N 사람들이 있고 그들은 무제한 공이 있지만 이번에는 바구니가 없습니다.

문제는 다음과 같습니다.

무제한 공과 다른 바구니가있는 n 사람이 있습니다. 사람들은 바구니에 공을 던집니다.

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

사람은 바구니 1, 2, 4,, 6,7, 14, 51, 32 사람 B에베이스에 던지기 3, 4, 6, 7, 14,15, 16, 64,43 사람 C Baskets에 던져진 3, 3, 3, 32 사람. 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]와 함께 파벌이라는 것을 알 수 있습니다.

Jackson의 답변에 대한 의견을 제시 한 예에서 일반적인 바구니 세트는 비어 있으므로이 사람들이 실제로 연결되어 있지 않다는 것을 알고 있습니다.

Answer 2

좋아, 나의 초기 아이디어; 이것을 가중 그래프로 모델링하십시오. 사람들을 정점으로 만들고 바구니를 공유 할 때 링크를 만듭니다. 그들이 여러 바구니를 공유하면 공유하는 각 바구니의 링크 무게를 늘립니다. 따라서 예에서 A와 B 사이의 가장자리의 무게는 4입니다.

그런 다음 그룹의 모든 사람이 얼마나 친절 해야하는지 결정하고, 그 값보다 무게를 가진 가장자리를 가지고 결과 그래프에서 클릭을 찾을 수 있습니다.