컬렉션의 집합이 컬렉션의 다른 집합의 하위 집합이 아니도록 컬렉션을 나타내는 추상 데이터 구조를 찾고 있습니다.컬렉션에 다른 컬렉션의 하위 집합 인 집합이없는 집합의 컬렉션
이 인서트 다음 조건이 충족되는 것을 의미 :
A. 이미 원래의 집합을 반환 다른 요소의 집합 인 요소를 삽입.
B. 다른 요소의 상위 집합 인 요소를 삽입하면 상위 집합이 추가되고 하위 집합이 제거 된 모음이 만들어집니다.
집합의 요소에 대한 정렬을 가정하면 접두사 트리를 사용하여 컬렉션을 나타낼 수 있습니다. 이것은 조건 A가 매우 신속하게 처리되도록 허용한다 (즉, 하위 집합을 삽입하는 것보다 조건을 검사하는 것이 더 이상 필요하지 않음) 그러나 조건 B를 충족하려면 시간이 걸린다.
B를 신속하게 충족시킬 수있는 데이터 구조가 있는지 궁금합니다.
사소한 접근법은 집합 목록을 유지하고 들어오는 모든 집합 (수신이 하위 집합인지 테스트)을 통해 선형 검색을 수행하는 것입니다.
이것은 분명히 선형 검색을 위해 O (n) 시간에서, 그리고 들어오는 세트의 크기에서 O (m) 크기로 실행됩니다. 따라서 O (n * m) 총 시간 (세트 수 대 각 세트의 크기).
물론 가장 확실한 최적화는 설정된 크기로 색인하는 것입니다. 그런 다음 각 들어오는 세트를 같거나 더 큰 크기의 것들에 대해서만 테스트합니다. (집합은 더 작은 집합의 부분 집합이 될 수 없습니다.)
마음에 오는 다음 최적화는 요소의 색인을 만드는 것입니다. 따라서 들어오는 각 세트에 대해 각 요소가 포함 된 각 세트의 교차점을 찾을 수 있습니다. 즉, 들어오는 집합 {a, b, c}에 대해 집합 {A}이 집합 A, B 및 D에 존재하고 요소 {B}가 B, E 및 F에 존재하고 {c} A, B, Z에 존재하면 ... 들어오는 세트는 B의 서브 세트 ({A, B, D}, {B, E, F} 및 {A, B, Z}의 교차)입니다.
그래서 나는 O (m * log (n)) 복잡함을 느낍니다. (각 들어오는 세트의 각 요소에 대한 해시 검색을 수행해야합니다.) 또한 삽입 순서는 동일해야합니다 (새 세트의 ID를 각 요소의 맵에 삽입). (Big-O 분석에서 2 * O (m log (n))은 물론 O (m log (n))로 줄어 듭니다.
K가 추가되는 요소의 크기 인 O (K)에서 작동 할 간단한 아이디어입니다. 개체> set_size
A와 B가 모두 O (K)이다.
개체는 {{a, b}, {b, c}, {a, c}}와 같이 여러 집합의 멤버가 될 수 있습니다. –
집합 A, B, ...의 개별 구성원이 별개의 (상대적으로) 소수에 매핑되고 각 집합 옆에 p (A), p (B) 등등. 부분 집합과 수퍼 집합은 p (X)가 p (Y)의 요소인지 아니면 그 반대인지에 따라 발견 될 수 있습니다.
내가 생각하기에 매우 큰 숫자로 끝날 수도 있지만 이론적으로는 작동합니다. 예를 들어
:
경우 [ABCD] -> [2 3 5 7], P (ABC) = 30, P (ABD)가 42, P (BC) = 15, P (ABCD) =210
숫자 NP가 완전하게 인수 분해되는 문제가 아닙니까? –
나누기 기능이있는 많은 수의 라이브러리를 사용하지 않는 경우! –
이 경우에는 문제가 단지 분할이 아니라 인수 분해가되어야한다고 덧붙여 야합니다. –
무슨 dorky 사이트! 나는 지금 등록을 마쳤습니다. 어제부터 물건에 대해 논평 할 수있게되었습니다. 그때까지, 그러나 ...
는@Stephen C : 나는 내가 explicator을 획득 한 것으로 보인다 내 영어가 적절한 것으로 생각하지만 그는 그러나, 밖으로 비트를 놓친하고 같이 읽어야 그의 코멘트는 다음과 같습니다
@Stephen C : 임의의 숫자를 찾는 요소는 실제로 NP 완료되었지만 여기에는 관련이 없습니다. 문제는 두 개의 숫자 중 더 작은 숫자가 더 큰 숫자를 정확하게 나누는 지 여부와 같습니다 ( 단순 계수 연산). 예를 들어, p (bc) = 15는 p (abcd) = 210, 의 제수이므로 bc는 abcd의 서브 세트입니다 (abd 및 abc와 같음). N 기존 컬렉션에 새로운 세트 S를 추가하는 설정
는 다수의 비교 및 분할 각 기존 항목 E에 관계없이 N.
대략 동일한 시간이 걸릴 것으로 가정하면, O (N) 인 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) 정확하게 추가 할 수 있습니다.
"B가 신속하게 충족되도록 허용"요구 사항입니까? 당신이 똑 바른 해결책이 무엇인지 상상할 수있는 것처럼 보입니다. 필자는 간단한 솔루션을 코딩 한 다음 공간/시간 성능 요구 사항을 충족하는지 확인합니다. 어쩌면 간단한 해결책으로도 충분할 것입니다. – shadit
접두어가 어떻게 도움이되는지 나는 모르겠다. 모든 하위 집합이 접두어가 아닙니다. –