모든 교차 세트의 합집합

StackOverflow https://stackoverflow.com/questions/967064

문제

여러 속성을 가진 개체 목록이 주어지면 교차하는 모든 하위 집합의 통합으로 생성된 집합 목록을 찾아야 합니다.

특히 이들은 각각 많은 속성을 갖는 Person 객체입니다.SSN, DLN 등과 같은 몇 가지 고유 식별자를 기반으로 '마스터' 세트 목록을 생성해야 합니다.

예를 들어, 개인 A와 개인 B가 동일한 SSN을 갖고 있는 경우 세트 i를 생성합니다.그런 다음 개인 B와 C가 동일한 DLN을 가지고 있으면 세트를 생성합니다. ii.개인 D와 E는 동일한 SSN을 가지고 있지만 이 SSN(및 기타 모든 식별자)은 개인 A, B 또는 C의 식별자와 일치하지 않습니다.교차하는 모든 하위 집합을 병합한 후 사람 A, B, C가 있는 한 세트와 사람 D, E가 있는 다른 세트로 끝납니다.

내 솔루션의 의사 코드는 다음과 같습니다.가능한 모든 교차 집합을 병합하는 더 효율적인 방법을 이미 생각해낸 사람이 있는지 궁금합니다.세트 사이의 링크는 X명이 될 수 있다는 점을 명심하십시오(예:A는 SSN으로 B와 일치하고 B는 DLN으로 C와 일치하며 C는 SSN으로 D와 일치하고 D는 다른 식별자로 E와 일치하므로 A-E가 한 세트에 포함됩니다.또한 이것이 구현될 언어가 집합 작업을 지원한다고 가정합니다.

bigSetList = array of all of the uniq Sets
fullyTested = false
while (bigSetList.size() > 1) or (fullyTested is false)
    foreach thisSet in bigSetList  order by size desc
        if count(sets that intersect with thisSet) > 0
            newThisSet = thisSet
            intersectingSets = []
            bigSetList.delete(thisSet)
            foreach testSet in bigSetList
                if thisSet.intersects(testSet)
                    newThisSet.addAll(testSet)
                    intersectingSets.push(testSetID)
                end if
            end
            bigSetList.delete(intersectingSets)
            bigSetList.push(newThisSet)
            bigSetList.sort()
            break
        end if
    end foreach
    fullyTested = true  // have looped through every set in the list and found 0 intersect partners
end
도움이 되었습니까?

해결책

원래 게시물에서 내 주석을 확장하려면 주어진 세트의 각 구성원이 해당 세트의 하나 이상의 다른 구성원과 하나 이상의 속성을 공유하는 세트 목록을 작성하려고합니다.

순진하게, 이것은 속성을 공유하는 모든 쌍을 찾아서 반복적으로 동일한 파트너가있는 쌍을 합쳐서 해결할 수 있습니다. 이것은 O (n^3)입니다 (N^2 쌍을 반복하려면 N^2, 멤버십을 결정하기 위해 최대 N 개별 세트).

이 문제를 결정하는 것으로 생각할 수도 있습니다. 그래프의 연결된 구성 요소, 여기서 모든 객체와 모든 고유 속성 값은 노드입니다. 각 객체는 각 속성 값에 연결됩니다. 그 그래프를 설정하는 데 선형 시간이 걸리며 폭 또는 깊이의 첫 번째 검색으로 선형 시간에 연결된 구성 요소를 결정할 수 있습니다.

다른 팁

고려 중인 Person 객체의 수에 비해 Person 객체에 대한 속성 집합이 상대적으로 적다고 생각합니다.Person 객체 목록을 여러 번 탐색하는 것을 줄이려면 Person을 가져와 해당 속성을 알려진 가능한 연결 목록에 넣은 후 다음 Person으로 이동할 수 있습니다.연속된 각 개인에 대해 이전 연결에 연결되어 있는지 확인합니다.그렇다면 가능한 연결에 고유한 특성을 추가합니다.한 번에 모든 Person 개체를 처리할 수 있어야 합니다.결과에 연결되지 않은 세트가 있을 수 있으므로 첫 번째 그래프를 만든 후 연결되지 않은 Person 개체를 검사하는 것이 좋습니다.

while (!people.isEmpty()) {
    Person first = people.get(0);
    people.remove(first);
    Set<Person> set = makeSet(first);
    for (Person person : people) {
        for (Person other : set) {
            if (person.isRelatedTo(other)) {
                set.add(person);
                people.remove(person);
            }
        }
    }
    sets.add(set);
}
for (Set<Person> a : sets) {
    for (Set<Person> b : sets.except(a)) {
        for (Person person : a)
            for (Person other : b) {
                if (person.isRelatedTo(other)) {
                    a.addAll(b);
                    b.clear();
                    sets.remove(b);
                    break;
                }
            }
    }
}

첫째, 식별자에 고유 한 계층 구조가 있습니까? 더 높은 정렬의 식별자가 더 낮은 종류의 동일한 식별자를 취소합니까? 예를 들어, A와 B가 동일한 SSN, B와 C가 동일한 DLN을 갖고 C와 D는 A와 B의 SSN과 일치하지 않는 동일한 SSN을 가지고 있으므로 두 그룹 또는 하나가 있다는 것을 의미합니까?

모순이 중요하지 않다고 가정하면 사용자 57368 (알 수없는 Google) 상태로 동등성 클래스를 다루고 있습니다. 동등성 클래스의 경우 사람들은 종종 노조 찾기 구조. 이 노동 조합을 수행하는 방법에 관해서는 A와 B가 모두 동일한 SSN을 가질 때 직접 링크 AB가 없다고 가정하기 때문에 즉시 사소하지는 않습니다. 대신, 우리 세트는 두 종류의 요소로 구성됩니다. 각 (attribute type, attribute value) = attribute 쌍은 요소입니다. 당신은 또한 해당 요소가 있습니다 object에스. 객체에 대한 속성 목록을 반복 할 때 노조를 수행하십시오. (object, attribute).

Union-Find 데이터 구조의 중요한 특징 중 하나는 결과 구조가 세트를 나타내는 것입니다. "어떤 세트는 in?" 이것으로 충분하지 않으면 알려 주시면 결과를 향상시킬 수 있습니다.

그러나 가장 중요한 특징은 알고리즘에 각 유니온 및 쿼리 작업에 대한 일정한 시간 동작과 유사한 것이 있다는 것입니다.

따라서 컬렉션 예제는 다음과 같이 보일 수 있습니다.

A { ss |-> 42, dl |-> 123 }
B { ss |-> 42, dl |-> 456 }
C { ss |-> 23, dl |-> 456 }
D { ss |-> 89, dl |-> 789 }
E { ss |-> 89, dl |-> 432 }

그런 다음 각 컬렉션을 멀티 컬렉션에 점진적으로 병합하거나 삽입하여 다중 수집을 구축하는 알고리즘을 사용하는 것이 좋습니다.

반복 1. 첫 번째 컬렉션은 유일한 다중 수집이됩니다.

{A} { ss |-> [42], dl |-> [123] }

반복 2. SSN이 이미 존재하기 때문에 다음 컬렉션을 첫 번째 컬렉션으로 병합합니다.

{A,B} { ss |-> [42], dl |-> [123,456] }

반복 3. DLN이 이미 존재하므로 다시 합병하십시오.

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }

반복 4. 일치하지 않기 때문에 새로운 다중 수집을 삽입하십시오.

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D}     { ss |-> [89],    dl |-> [789]     }

반복 5. SSN이 있기 때문에 두 번째 멀티 컬렉션과 합병하십시오.

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D,E}   { ss |-> [89],    dl |-> [432,789] }

따라서 각 반복 (각 컬렉션 당 하나)에서 식별해야합니다. 모두 처리중인 컬렉션과 공통점이있는 다중 수집 및 병합 모두 이것들과 함께.

일반적으로 k 수의 속성이 상수가있는 N 컬렉션이있는 경우이 알고리즘은 시간 O (NNK) = O (N)로 실행됩니다.2). 모든 속성 값이 뚜렷한 경우 최악의 행동이 종료됩니다. 속성 값 사이에 더 많은 공유가 있으면 속성 값 세트의 멤버십을 삽입하고 결정하는 데 걸리는 시간 (예 : [23,42])가 지배적 인 요소가되므로 속성 값 세트가 효율적이어야합니다.

사용하는 경우 최적의 분리 세트, 그런 다음 각각의 찾기 또는 병합 작업은 상각 된 시간 O (α (n))로 실행됩니다.

따라서, 각 반복마다 최대 N 다중 수집이있을 것이다 (지금까지 다중 수집이 병합되지 않은 상황). 새 컬렉션을 다중 수집에 통합하려면 각각의 다중 수집 k 세트에서 찾기 작업을 수행하여 병합 될 모든 다중 수집을 식별해야합니다. . 이 방법으로 발견 된 최대 K 다중 수집을 병합하면 O (k2α (n)).

따라서 모든 반복에 대해 시간은 O (n (nkα (n)+k2α (n))) = O (n (nkα (n))) = O (n2Kα (n)) = O (n2k는 일정하기 때문에 α (n)).

모든 실제 목적을 위해 α (n)도 일정하기 때문에 총 시간은 O (n2).

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top