배열의 가장 큰 공통 하위 집합을 찾는 Objective-C 알고리즘?

Question

저는 현재 최대 배열 다중 배열의 하위 집합을 찾는 데 효율적인 솔루션이 필요합니다.

예 :사용자 Chris는 공통 관심사를 가진 다른 사용자 (가장 일반적인 것부터 가장 일반적인 것까지)를 찾고 싶다고 가정 해 보겠습니다. 그의 관심사 배열을 다른 사용자의 배열과 비교하고 가장 작은 공통 하위 집합을 가장 작은 공통 하위 집합으로 찾아야합니다.

크리스 {볼링, 게임, 스케이트, 실행}

그리고 데이터베이스의 다른 사용자.

이

브래드 {앉아 볼링, 점프, 걷기,}
요한 {볼링, 게임, 스케이트, 먹는}
가 사라 {볼링, 게임은, 그리기, 코딩}

그래서 크리스가

존 (John), 사라 (Sarah), 브래드 (Brad)와 각각 가장 공통적 인 관심사입니다.

어떻게 Objective-C에서이 작업을 수행 할 수 있습니까? 모든 포인터가 좋을 것입니다.

Answer 1

설정된 교차점의 카디널리티를 찾는 알고리즘을 찾고 있습니다.

설정 표현에 따라 다른 방법을 선택할 수 있습니다. 이것에 대한 가장 뛰어난 표현은 정수로 비트를 사용하는 것이지만 가능한 관심사의 수가 64를 초과하면 구현하기가 쉽지 않을 수 있습니다.

을 구현하는 간단한 방법은 다음과 같이, NSMutableSet과 같습니다

// Prepare the individual lists 
NSArray *chris = @[@"bowling", @"gaming", @"skating", @"running"]; 
NSArray *brad = @[@"bowling", @"jumping", @"walking", @"sitting"]; 
// Obtain the intersection 
NSMutableSet *common = [NSMutableSet setWitArray:chris]; 
[common intersectSet:[NSSet setWithArray:brad]]; 
NSLog(@"Common interest count: %i", common.count);