Set consolidation: Difference between revisions

=={{header|TXR}}==

Using most basic disjoint-set algorithm (no rank join or path compression).

<lang txr>@(do

(defun mkset (p x) (if (not [p x]) (set [p x] x)))

(defun fnd (p x) (if (eq [p x] x) x (fnd p [p x])))

(defun uni (p x y)

(let ((xr (fnd p x)) (yr (fnd p y)))

(set [p xr] yr)))

(defun consoli (sets)

(let ((p (hash)))

(each ((s sets))

(each ((e s))

(mkset p e)

(uni p e (car s))))

(hash-values

[group-by (op fnd p) (hash-keys

[group-by identity (flatten sets)])])))

;; tests

(each ((test '(((a b) (c d))

((a b) (b d))

((a b) (c d) (d b))

((h i k) (a b) (c d) (d b) (f g h)))))

(format t "~s -> ~s\n" test (consoli test))))</lang>

Output:

<pre>((a b) (c d)) -> ((d c) (b a))

((a b) (b d)) -> ((d b a))

((a b) (c d) (d b)) -> ((d c b a))

((h i k) (a b) (c d) (d b) (f g h)) -> ((d c b a) (g f k i h))</pre>