컬렉션의 다른 하위 집합 인 세트가없는 세트 모음

Question

컬렉션의 세트가 컬렉션의 다른 세트의 하위 집합이되도록 세트 컬렉션을 나타내는 추상 데이터 구조를 찾고 있습니다.

이는 다음 조건을 삽입 할 때 다음 조건이 충족됩니다.

A. 이미 다른 요소의 하위 집합 인 요소를 삽입하면 원래 컬렉션이 반환됩니다.

B. 다른 요소의 슈퍼 세트 인 요소를 삽입하면 슈퍼 세트가 추가되고 서브 세트가 제거 된 채택이 발생합니다.

세트의 요소에 대한 순서를 가정하면 접두사 트리를 사용하여 컬렉션을 나타낼 수 있습니다. 이렇게하면 조건 A가 매우 빨리 처리 될 수 있습니다 (즉, 하위 집합을 삽입하는 것보다 조건을 확인하는 데 더 이상 조건을 확인하지 않아도됩니다) 그러나 충족 조건 B에는 시간이 걸립니다.

B를 신속하게 충족시킬 수있는 데이터 구조가 있는지 궁금합니다.

Answer 1

사소한 접근 방식은 세트 목록을 유지하고 모든 들어오는 세트에 대해이를 통해 선형 검색을 수행하는 것입니다 (수신이 서브 세트 인 경우 테스트).

이것은 선형 검색을위한 O (n) 시간과 수신 세트의 크기에 대해 O (m) 크기로 실행됩니다. 따라서 O (n*m) 총 시간 (세트 수와 각 세트의 크기).

물론 가장 명백한 최적화는 세트 크기로 인덱싱하는 것입니다. 그런 다음 수신 세트가 크기가 같거나 더 큰 세트에 대해서만 테스트합니다. (세트는 더 작은 세트의 하위 집합이 될 수 없습니다, duh!).

떠오르는 다음 최적화는 요소 색인을 만드는 것입니다. 따라서 각 들어오는 세트에 대해 각 요소를 포함하는 각 세트의 교차점을 찾을 수 있습니다. 다시 말해서, 들어오는 세트 {a, b, c}의 경우, 우리는 요소 {a}가 세트 a, b 및 d에 존재한다는 것을 알 수 있습니다. A, B 및 Z에 존재합니다 ... 그러면 들어오는 세트는 B의 서브 세트입니다 ({a, b, d}, {b, e, f} 및 {a, b, z}의 교차점).

그래서 그것은 나에게 O (m*log (n)) 복잡성처럼 들립니다. (우리는 수신 세트의 각 요소에서 해시 검색을 수행해야합니다). 삽입도 같은 순서에 있어야합니다 (새 세트의 ID를 각 요소의 맵에 삽입). (big-o 분석에서 2*o (mlog (n))는 O (m)로 줄어 듭니다.물론 로그 (n)).

Answer 2

k가 추가되는 요소의 크기 인 O (k)에서 작동하는 사소한 아이디어.

• 원하는 방식으로 세트를 유지하십시오
• set_id-> set_size의지도를 유지하십시오
• Object-> set_id의지도를 유지하십시오

A와 B는 모두 O (k)입니다.

Answer 3

세트의 개별 멤버가 A, B, ...은 별개의 (그리고 상대적으로) 소수에 매핑되고 각 세트와 함께 모든 멤버의 제품을 p (a), p (b) 등으로 저장합니다. p (x)가 p (y)의 계수인지 그 반대의 계수에 의해 서브 세트 및 초점 세트를 찾을 수 있습니다.

당신은 내가 생각하는 아주 많은 숫자로 끝날 수 있지만 이론적으로는 작동합니다.

예를 들어:

if [abcd] -> [2 3 5 7], p (abc) = 30, p (abd) = 42, p (bc) = 15, p (abcd) = 210

Answer 4

얼마나 멍청한 사이트! 이제 등록 했으므로 어제부터 물건에 대해 언급 할 수 있습니다. 그러나 그때까지 ...

@Stephen C : 영어가 적절하다고 생각하지만 설명자를 얻은 것 같습니다. 그러나 그는 비트를 놓쳤으며 그의 의견은 다음과 같이 읽어야합니다.

---

@Stephen C : 임의의 숫자의 요인을 찾는 것은 실제로 NP가 완료되지만 여기서는 관련이 없습니다. 문제는 두 숫자 중 소규모가 더 큰 단순한 모듈러스 작업을 정확하게 나누는 지 여부입니다. 예를 들어, p (bc) = 15는 p (ABCD) = 210의 제수이므로 BC는 ABCD의 서브 세트입니다 (세트 ABD 및 ABC).

기존 N 세트 컬렉션에 새 세트를 추가하는 것은 O (n)입니다. 많은 수의 비교와 분할이 N에 관계없이 거의 동일하게 걸리는다 고 가정합니다.

세트 모음의 기존 항목 E에 대해 p (s) <p (e) 및 p (s)가 p (e)를 정확하게 나누는 경우 중지하십시오. p (s) = p (e) 인 경우 중지하십시오. p (s)> p (e)와 p (e)가 p (s)를 정확하게 나누면 e를 제거하십시오. 컬렉션의 끝에 도착하면 S를 추가하십시오. 많은 Bignums가 작동합니다.

---

@JL : 내 현장 스토커가되고 싶다면 1) 가치를 추가하십시오. 2) 정확하게.