Set consolidation: Difference between revisions
Content added Content deleted
(New task and Python solution.) |
(→{{header|Python}}: One enumeration too many.) |
||
Line 72: | Line 72: | ||
for i, s1 in enumerate(setlist): |
for i, s1 in enumerate(setlist): |
||
if s1: |
if s1: |
||
for |
for s2 in setlist[i+1:]: |
||
intersection = s1.intersection(s2) |
intersection = s1.intersection(s2) |
||
if intersection: |
if intersection: |
Revision as of 10:52, 7 May 2012
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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 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>