시 동아리

서로소 집합(유니온 파인드 구조)은 여러 값을 겹치지 않는 그룹으로 나눠서 보관하고, "이 두 값이 같은 그룹에 있나요?"라는 질문 하나에 빠르게 답해 줘요. disjoint-sets 보캐불러리에 들어 있어요.

서로소 집합 만들기

<disjoint-set>은 빈 구조를 만들어요. 값, 즉 애텀은 add-atom으로 하나씩 추가하거나 add-atoms로 시퀀스에서 한꺼번에 추가해요. 각 애텀은 처음에는 자기 혼자만의 그룹에 있어요.

<disjoint-set> ( -- disjoint-set )
add-atom       ( atom disjoint-set -- )
add-atoms      ( seq disjoint-set -- )

USING: disjoint-sets ;

<disjoint-set>
{ 1 2 3 } over add-atoms   ! 1, 2 and 3 each in their own group

서로소 집합은 가변적이에요. add-atom, add-atoms, equate는 새로운 집합을 반환하는 대신 그 자리에서 내용을 바꿔요. 이 워드들이 서로소 집합을 스택에서 꺼내 쓴 뒤에도 그 집합을 다시 스택에 남겨 두고 싶을 때 keep이 유용해요.

그룹 합치기

equate는 두 애텀이 각각 속한 그룹을 하나로 합쳐요. 합치는 것은 추이적이에요. 두 애텀을 합친 다음 그중 하나를 세 번째 애텀과 합치면, 셋 모두 한 그룹에 들어가요.

equate ( atom1 atom2 disjoint-set -- )

대표

각 그룹에는 기준이 되는 구성원이 하나 있는데, 그것이 그 그룹의 대표예요. representative는 그 대표를 반환하고, 두 애텀이 같은 그룹에 속하는 것은 두 애텀의 대표가 같을 때와 정확히 일치해요.

representative ( atom disjoint-set -- representative )

USING: disjoint-sets ;

<disjoint-set>
{ 1 2 3 } over add-atoms
1 2 pick equate
1 over representative .   ! => 1
2 over representative .   ! => 1   (same representative as 1)
3 over representative .   ! => 3   (still on its own)

그룹이 어떤 애텀을 대표로 고르는지는 내부 구현의 세부 사항이에요. 특정 애텀이 대표로 선택되는지에 기대지 말고, 같은 그룹에 있는 두 애텀의 대표가 서로 같다는 점에만 기대해요.