On 02/21/2015 02:46 PM, 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 can't see where you've defined "this" yet. I think you're trying to
find all combinations of sets that are "related", and that you're
assuming some of them won't be. So perhaps you're trying to build
"islands" of related sets, and you want each of those islands to be of
maximal size.
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.
Seems like you can have a doubly-nested loop, where your inner loop
collects all the sets that are related to the one in the outer loop.
You label each group with an island-number, where the island number is
simply the lowest number set that's on the island.
It's still not clear what you do with each of those islands, but the
"superset" you refer to before is simply the OR of everything on the island.
Perhaps you want to show all smaller supersets that are composed of at
least two sets of an island. That becomes a fairly simple power-of-two
iteration of those sets, where you throw out the case where the index is
a power of two (ie. contains only one set).
As you say, calculating the union or intersection of the various sets in
python is trivial.
--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list
