Algorithm for Creating Supersets of Smaller Sets Based on Common Elements
Ethan Furman
ethan at stoneleaf.us
Sat Feb 21 15:11:12 EST 2015
On 02/21/2015 11:46 AM, 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?
Use a Counter (collections.Counter), add all sets, then keep any keys with a count of 2 or more.
--
~Ethan~
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: OpenPGP digital signature
URL: <http://mail.python.org/pipermail/python-list/attachments/20150221/a7186e97/attachment.sig>
More information about the Python-list
mailing list