Set consolidation
You are encouraged to solve this task according to the task description, using any language you may know.
Given two sets of items then if any item is common to any set then the result of applying consolidation to those sets is a set of sets whose contents is:
- The two input sets if no common item exists between the two input sets of items.
- The single set that is the union of the two input sets if they share a common item.
Given N sets of items where N>2 then the result is the same as repeatedly replacing all combinations of two sets by their consolidation until no further consolidation between set pairs is possible. If N<2 then consolidation has no strict meaning and the input can be returned.
- Example 1:
- Given the two sets {A,B} and {C,D} then there is no common element between the sets and the result is the same as the input.
- Example 2:
- Given the two sets {A,B} and {B,D} then there is a common element B between the sets and the result is the single set {B,D,A}. (Note that order of items in a set is immaterial: {A,B,D} is the same as {B,D,A} and {D,A,B}, etc).
- Example 3:
- Given the three sets {A,B} and {C,D} and {D,B} then there is no common element between the sets {A,B} and {C,D} but the sets {A,B} and {D,B} do share a common element that consolidates to produce the result {B,D,A}. On examining this result with the remaining set, {C,D}, they share a common element and so consolidate to the final output of the single set {A,B,C,D}
- Example 4:
- The consolidation of the five sets:
- {H,I,K}, {A,B}, {C,D}, {D,B}, and {F,G,H}
- Is the two sets:
- {A, C, B, D}, and {G, F, I, H, K}
See also:
C
<lang c>#include <stdio.h>
- define s(x) (1U << ((x) - 'A'))
typedef unsigned int bitset;
int consolidate(bitset *x, int len) { int i, j; for (i = len - 2; i >= 0; i--) for (j = len - 1; j > i; j--) if (x[i] & x[j]) x[i] |= x[j], x[j] = x[--len]; return len; }
void show_sets(bitset *x, int len) { bitset b; while(len--) { for (b = 'A'; b <= 'Z'; b++) if (x[len] & s(b)) printf("%c ", b); putchar('\n'); } }
int main(void) { bitset x[] = { s('A') | s('B'), s('C') | s('D'), s('B') | s('D'), s('F') | s('G') | s('H'), s('H') | s('I') | s('K') };
int len = sizeof(x) / sizeof(x[0]);
puts("Before:"); show_sets(x, len); puts("\nAfter:"); show_sets(x, consolidate(x, len)); return 0; }</lang>
Ela
This solution emulate sets using linked lists: <lang ela>open Core
let merge [] ys = ys
merge (x::xs) ys | x `elem` ys = merge xs ys
| else = merge xs (x::ys)
let consolidate (_::[])@xs = xs
consolidate (x::xs) = conso [x] (consolidate xs)
where conso xs [] = xs
conso (x::xs)@r (y::ys) | intersect x y <> [] = conso ((merge x y)::xs) ys
| else = conso (r ++ [y]) ys</lang>
Usage:
In this example sets are filled with variants (somewhat similar to atoms in Lisp). One can use any other values (such as strings or chars) as well. <lang ela>open Con
consolidate [[H,I,K], [A,B], [C,D], [D,B], [F,G,H]] |> writen $ consolidate [[A,B], [B,D]] |> writen</lang>
- Output:
[[K,I,F,G,H],[A,C,D,B]] [[A,B,D]]
Go
<lang go>package main
import "fmt"
type set map[string]bool
var testCase = []set{
set{"H": true, "I": true, "K": true},
set{"A": true, "B": true},
set{"C": true, "D": true},
set{"D": true, "B": true},
set{"F": true, "G": true, "H": true},
}
func main() {
fmt.Println(consolidate(testCase))
}
func consolidate(sets []set) []set {
setlist := []set{}
for _, s := range sets {
if s != nil && len(s) > 0 {
setlist = append(setlist, s)
}
}
for i, s1 := range setlist {
if len(s1) > 0 {
for _, s2 := range setlist[i+1:] {
if s1.disjoint(s2) {
continue
}
for e := range s1 {
s2[e] = true
delete(s1, e)
}
s1 = s2
}
}
}
r := []set{}
for _, s := range setlist {
if len(s) > 0 {
r = append(r, s)
}
}
return r
}
func (s1 set) disjoint(s2 set) bool {
for e := range s2 {
if s1[e] {
return false
}
}
return true
}</lang>
- Output:
[map[A:true C:true B:true D:true] map[G:true F:true I:true H:true K:true]]
Python
Iterative
The docstring contains solutions to all the examples as well as a check to show the order-independence of the sets given to the consolidate function. <lang python>def consolidate(sets):
>>> # Define some variables
>>> A,B,C,D,E,F,G,H,I,J,K = 'A,B,C,D,E,F,G,H,I,J,K'.split(',')
>>> # Consolidate some lists of sets
>>> consolidate([{A,B}, {C,D}])
[{'A', 'B'}, {'C', 'D'}]
>>> consolidate([{A,B}, {B,D}])
[{'A', 'B', 'D'}]
>>> consolidate([{A,B}, {C,D}, {D,B}])
[{'A', 'C', 'B', 'D'}]
>>> consolidate([{H,I,K}, {A,B}, {C,D}, {D,B}, {F,G,H}])
[{'A', 'C', 'B', 'D'}, {'G', 'F', 'I', 'H', 'K'}]
>>> consolidate([{A,H}, {H,I,K}, {A,B}, {C,D}, {D,B}, {F,G,H}])
[{'A', 'C', 'B', 'D', 'G', 'F', 'I', 'H', 'K'}]
>>> consolidate([{H,I,K}, {A,B}, {C,D}, {D,B}, {F,G,H}, {A,H}])
[{'A', 'C', 'B', 'D', 'G', 'F', 'I', 'H', 'K'}]
>>> # Confirm order-independence
>>> from copy import deepcopy
>>> import itertools
>>> sets = [{H,I,K}, {A,B}, {C,D}, {D,B}, {F,G,H}, {A,H}]
>>> answer = consolidate(deepcopy(sets))
>>> for perm in itertools.permutations(sets):
assert consolidate(deepcopy(perm)) == answer
>>> answer
[{'A', 'C', 'B', 'D', 'G', 'F', 'I', 'H', 'K'}]
>>> len(list(itertools.permutations(sets)))
720
>>>
setlist = [s for s in sets if s]
for i, s1 in enumerate(setlist):
if s1:
for s2 in setlist[i+1:]:
intersection = s1.intersection(s2)
if intersection:
s2.update(s1)
s1.clear()
s1 = s2
return [s for s in setlist if s]</lang>
Recursive
<lang python>def conso(s): if len(s) < 2: return s
r, b = [s[0]], conso(s[1:]) for x in b: if r[0].intersection(x): r[0].update(x) else: r.append(x) return r</lang>
Tcl
This uses just the recursive version, as this is sufficient to handle substantial merges. <lang tcl>package require struct::set
proc consolidate {sets} {
if {[llength $sets] < 2} {
return $sets
}
set r [list {}]
set r0 [lindex $sets 0]
foreach x [consolidate [lrange $sets 1 end]] {
if {[struct::set size [struct::set intersect $x $r0]]} { struct::set add r0 $x } else { lappend r $x }
} return [lset r 0 $r0]
}</lang> Demonstrating: <lang tcl>puts 1:[consolidate {{A B} {C D}}] puts 2:[consolidate {{A B} {B D}}] puts 3:[consolidate {{A B} {C D} {D B}}] puts 4:[consolidate {{H I K} {A B} {C D} {D B} {F G H}}]</lang>
- Output:
1:{A B} {C D}
2:{D A B}
3:{D A B C}
4:{H I F G K} {D A B C}