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

Groups > comp.lang.python > #86066

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

Show key headers only | View raw

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

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