Set consolidation
Set consolidation
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
See also:
Given two sets of items then if any item is common to any set then the result of applying consolidation to those sets is:
- The two input sets if no common item exists between those two sets of items.
- Or one set of all the items from both sets if they share a common item.
Given N sets of items 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.
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 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 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'}
Python
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 >>> import itertools >>> sets = [{H,I,K}, {A,B}, {C,D}, {D,B}, {F,G,H}, {A,H}] >>> answer = consolidate(sets) >>> for perm in itertools.permutations(sets): assert consolidate(perm) == answer
>>> len(list(itertools.permutations(sets))) 720 >>> setlist = [s for s in sets if s] for i, s1 in enumerate(setlist): if s1: for j, s2 in enumerate(setlist[i+1:], i+1): intersection = s1.intersection(s2) if intersection: s2.update(s1) s1.clear() s1 = s2 return [s for s in setlist if s]
</lang>