Set consolidation
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.
You are encouraged to solve this task according to the task description, using any language you may know.
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:
Bracmat
<lang bracmat>( ( consolidate
= a m z mm za zm zz
. ( removeNumFactors
= a m z
. !arg:?a+#%*?m+?z
& !a+!m+removeNumFactors$!z
| !arg
)
& !arg
: ?a
%?`m
( %?z
& !m
: ?
+ ( %@?mm
& !z:?za (?+!mm+?:?zm) ?zz
)
+ ?
)
& consolidate$(!a removeNumFactors$(!m+!zm) !za !zz)
| !arg
)
& (test=.out$(!arg "==>" consolidate$!arg)) & test$(A+B C+D) & test$(A+B B+D) & test$(A+B C+D D+B) & test$(H+I+K A+B C+D D+B F+G+H) );</lang> Output:
A+B C+D ==> A+B C+D A+B B+D ==> A+B+D A+B C+D B+D ==> A+B+C+D H+I+K A+B C+D B+D F+G+H ==> F+G+H+I+K A+B+C+D
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]]
OCaml
<lang ocaml>let join a b =
List.fold_left (fun acc v -> if List.mem v acc then acc else v::acc ) b a
let share a b = List.exists (fun x -> List.mem x b) a
let extract p lst =
let rec aux acc = function | x::xs -> if p x then Some (x, List.rev_append acc xs) else aux (x::acc) xs | [] -> None in aux [] lst
let consolidate sets =
let rec aux acc = function
| [] -> List.rev acc
| x::xs ->
match extract (share x) xs with
| Some (y, ys) -> aux acc ((join x y) :: ys)
| None ->
aux (x::acc) xs
in
aux [] sets
let print_sets sets =
print_string "{ ";
List.iter (fun set ->
print_string "{";
print_string (String.concat " " set);
print_string "} "
) sets;
print_endline "}"
let () =
print_sets (consolidate [["A";"B"]; ["C";"D"]]);
print_sets (consolidate [["A";"B"]; ["B";"C"]]);
print_sets (consolidate [["A";"B"]; ["C";"D"]; ["D";"B"]]);
print_sets (consolidate [["H";"I";"K"]; ["A";"B"]; ["C";"D"]; ["D";"B"];
["F";"G";"H"]]);
- </lang>
Output:
{ {A B} {C D} }
{ {A B C} }
{ {B A C D} }
{ {K I F G H} {B A C D} }
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}