Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #86065

Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

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~

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Algorithm for Creating Supersets of Smaller Sets Based on Common Elements "TommyVee" <xxxxxxxx@xxxxxx.xxx> - 2015-02-21 14:46 -0500
  Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements Joel Goldstick <joel.goldstick@gmail.com> - 2015-02-21 15:06 -0500
  Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements Ethan Furman <ethan@stoneleaf.us> - 2015-02-21 12:11 -0800
  Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements Dave Angel <davea@davea.name> - 2015-02-21 15:18 -0500
  Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-21 22:40 +0000
  Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements "TommyVee" <xxxxxxxx@xxxxxx.xxx> - 2015-02-21 19:07 -0500
  Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-02-22 15:02 +1100
    Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements wxjmfauth@gmail.com - 2015-02-22 00:15 -0800
  Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements Peter Pearson <pkpearson@nowhere.invalid> - 2015-02-22 16:49 +0000
  Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements duncan smith <buzzard@invalid.invalid> - 2015-02-22 17:02 +0000

csiph-web