Set consolidation

Set consolidation
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 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 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 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'}

Go

Translation of: Python

<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>