On 21/02/2015 19:46, TommyVee wrote:
Start off with sets of elements as follows:
1. A,B,E,F
2. G,H,L,P,Q
3. C,D,E,F
4. E,X,Z
5. L,M,R
6. O,M,Y
Note that sets 1, 3 and 4 all have the element 'E' in common, therefore
they are "related" and form the following superset:
A,B,C,D,E,F,X,Z
Likewise, sets 2 and 5 have the element 'L' in common, then set 5 and 6
have element 'M' in common, therefore they form the following superset:
G,H,L,M,O,P,Q,R,Y
I think you get the point. As long as sets have at least 1 common
element, they combine to form a superset. Also "links" (common
elements) between sets may go down multiple levels, as described in the
second case above (2->5->6). Cycles thankfully, are not possible.
BTW, the number of individual sets (and resultant supersets) will be
very large.
I don't know where to start with this. I thought about some type of
recursive algorithm, but I'm not sure. I could figure out the Python
implementation easy enough, I'm just stumped on the algorithm itself.
Anybody have an idea?
Thanks, Tom
A naive approach but should give you something to think about.
from collections import defaultdict
sets = ({'A','B','E','F'},
{'G','H','L','P','Q'},
{'C','D','E','F'},
{'E','X','Z'},
{'L','M','R'},
{'O','M','Y'})
d = defaultdict(list)
for i, aSet in enumerate(sets):
for a in aSet:
d[a].append(i)
superSets = []
for k in d:
if len(d[k]) > 1:
superSet = set()
for i in d[k]:
superSet |= sets[i]
superSets.append(superSet)
--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.
Mark Lawrence
--
https://mail.python.org/mailman/listinfo/python-list
