# Programming-Idioms

This language bar is your friend. Select your favorite languages!

# Idiom #187 Disjoint Set

Disjoint Sets hold elements that are partitioned into a number of disjoint (non-overlapping) sets.

``````public class DisjointSetElement {
private DisjointSetElement representative = this;

public DisjointSetElement getRepresentative() {
if (representative != this) {
representative = representative.getRepresentative();
}
return representative;
}

public void union(DisjointSetElement other) {
other.getRepresentative().representative = getRepresentative();
}
}
``````
``````(defstruct disjoint-set
elements)

(defun make-disjoint-set (elements)
(make-disjoint-set :elements elements))

(defun partition (disjoint-set)
(loop for element in (disjoint-set-elements disjoint-set)
collect
(let ((found (find element (mapcar #'first (rest disjoint-set))
:test #'equal)))
(if found
(acons element element found :test #'equal)
(acons element element nil :test #'equal)))))``````
``````use feature 'say';
use Graph::UnionFind;``````
``````my @vert = (1..5);
my @edges = ( [1, 2], [2, 3], [4, 5] );

\$uf->add( \$_ )   for @vert;
\$uf->union( \$_ ) for @edges;

# find and consolidate partitions into a hash
my %part;
foreach my \$v( @vert ) {
my @pa = \$uf->find(\$v);
my \$p = shift @pa;
\$part{\$p} //= [];
push @{ \$part{\$p} }, \$v;
}

foreach my \$k (sort keys %part) {
my \$vals = join ' ', @{ \$part{\$k} };
say "\$k : \$vals";
}
# prints:
#   2 : 1 2 3
#   5 : 4 5
``````
``````class UnionFind:
def __init__(self, size):
self.rank = [0] * size
self.p = [i for i in range(size)]

def find_set(self, i):
if self.p[i] == i:
return i
else:
self.p[i] = self.find_set(self.p[i])
return self.p[i]

def is_same_set(self, i, j):
return self.find_set(i) == self.find_set(j)

def union_set(self, i, j):
if not self.is_same_set(i, j):
x, y = self.find_set(i), self.find_set(j)
``````
``require 'set'``
``a.disjoint?(b)``

Shaftway