4
\$\begingroup\$

The goal of this challenge is to compute the set of equivalence classes over the transitive closure of a symmetric, reflexive relation. For those who don't know what that means, here is a brief introduction into the relevant terms:

A relation ◊ is symmetric if abba. It is reflexive if each object is related to itself, i.e. aa always holds. It is transitive if abbcac, i.e. if a is related to b and b is related to c, then a is related to c. An equivalence relation is a relation that is symmetric, reflexive and transitive.

The transitive closure ◊* of ◊ is a transitive relation such that a ◊* b holds if and only if there is a (possibly empty) series of objects c1, c2, ..., cn such that ac1c2 ◊ ··· ◊ cnb. The transitive closure of a symmetric, reflexive relation is an equivalence relation.

Let ≡ be an equivalence relation over the set S. An equivalence class a of an object a over the relation ≡ is the largest subset of S such that ax for all xS or formally: a = { x | xS, ax }. All elements of a are equivalent to one another.

The set of equivalence classes S/≡ of ≡ over S is the set of equivalence classes of all members of S.

Constraints

In this task, your objective is to write a function that takes a binary relation ≅ and a finite non-empty set S. You may take input in a suitable way and choose a suitable data-structure for S (e.g. an array or a linked list). Assume that ≅ is a symmetric, reflexive relation over S. Your function should return or print out the set of equivalence classes over S of the transitiveclosure of ≅. You may choose a suitable output format or data structure for the result. As the result is a set, each object in S may appear only once.

You may not use library routines or other builtin functionality to find the components of a graph or related things.

Winning condition

The shortest answer in octets wins. The most elegant answer is chosen in case of a tie.

Sample input

The reflexive and symmetric members of ≅ have been omitted for brevity.

S1 = {A, B, C, D, E, F, G, H}
1 = {(A, B), (B, C), (B, E), (D, G) (E, H)}
S1/≅1* = {{A, B, C, E, H}, {D, G}, {F}}.

S2 = {α, β, γ, δ, ε, ζ, η, θ, ι, κ}
2 = {(α, ζ), (α, ι), (β, γ), (β, ε), (γ, δ), (γ, ε), (ζ, θ), (η, κ), (θ, ι)}
S2/≅2* = {{α, ζ, θ, ι}, {β, γ, δ, ε}, {η, κ}}

S3 = {♠, ♣, ♥, ♦}
3 = {}
S3/≅3* = {{♠}, {♣}, {♥}, {♦}}

S4 = {Α, Β, Γ, Δ, Ε, Ζ, Η, Θ, Ι, Κ, Λ}
4 = {(Α, Ε), (Β, Ζ), (Γ, Η), (Δ, Θ), (Ε, Ι), (Ζ, Κ), (Η, Λ), (Θ, Α), (Ι, Β), (Κ, Γ), (Λ, Δ)}
S4/≅4* = {{Α, Β, Γ, Δ, Ε, Ζ, Η, Θ, Ι, Κ, Λ}}

\$\endgroup\$
  • \$\begingroup\$ Here's another connected components question, with the difference that it doesn't ask for the members of the components. Not sure if everyone would consider that a duplicate. \$\endgroup\$ – feersum Jan 23 '16 at 14:20
  • 1
    \$\begingroup\$ I like the idea of having a dedicated (and separate) connected components challenge that asks for the actual components and not just their number. But since this challenge is just that, I don't think it benefits from being wrapped in a lot of notation about equivalence relations. That's a nice application, but it increases the entry barrier for people without that kind of background unnecessarily. \$\endgroup\$ – Martin Ender Jan 23 '16 at 14:57
  • 1
    \$\begingroup\$ @FUZxxl That's a noble intent, but I don't think there's much to discover here. Even if you never think about the relation to graphs and just implemented the first solution that came to your mind, you'd still have computed the connected components of a graph, because the problems are completely equivalent. It's not like it's an interesting shortcut to the problem that can be discovered, it's just a different way to present it. I don't think that's a good reason to artificially make the problem more complicated than it needs to be. \$\endgroup\$ – Martin Ender Jan 23 '16 at 15:17
  • 1
    \$\begingroup\$ Another thing: the Unicode stuff is a nice alternative to LaTeX but I think it might hinder the (technical) accessibility of the spec. Someone who can't display all of the characters will have no clue what's going on, and in particular, it's impossible to copy the test cases into a potential solution. Everyone will have to replace the letters with numbers manually (unless they're using Mathematica I guess), before they can use the test cases. If you used numbers to identify the elements, then apart from substituting some delimiters, most people could use the test cases out of the box. \$\endgroup\$ – Martin Ender Jan 23 '16 at 15:19
  • 1
    \$\begingroup\$ The "hull" terminology is new to me, and Google search results for "transitive hull" seem only to give pages which talk about "transitive closure" without mentioning the word "hull" anywhere. I think that's fairly good evidence that it would be clearer to talk about closures than hulls. \$\endgroup\$ – Peter Taylor Jan 23 '16 at 20:57
1
\$\begingroup\$

Pyth, 50 29 bytes

JchQ1FNeQAmf/@JTd0N XGJ.(JH;J

Input is expected to be a list of two elements where the first element is a list of all the objects in S, and the second element is a list of all the members in ≅, represented as lists. So for the first example, the input is

[["A", "B", "C", "D", "E", "F", "G", "H"], [["A", "B"], ["B", "C"], ["B", "E"], ["D", "G"], ["E", "H"]]]

Explanation:

                               Implicit assignment of Q to input, so head(Q) is S and end(Q) is ≅
JchQ1                          Assign J to chop(head(Q),1) e.g. [1,2,3] => [[1],[2],[3]]
     FNeQ                      For N in end(Q)
         A                       Assign [H,G] to following list
          m       N                Map following function over N
           f     0                   Return first T where following function of T starting at 0,1,2... is truthy         
            /@JTd                      lambda d: true if d is J[T]
                    XGJ.(JH;     Append J[H] to J[G] and pop J[H]
                            J  Print J

Note that if transitive or reflexive members (i.e. redundant) members of ≅ are included, my code should output junk.

You can try it out here.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.