Path: csiph.com!usenet.pasdenom.info!gegeweb.org!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Sat, 21 Feb 2015 15:18:54 -0500
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Algorithm for Creating Supersets of Smaller Sets Based on Common Elements
References: <Bg5Gw.1344030$No4.494335@fx19.iad>
In-Reply-To: <Bg5Gw.1344030$No4.494335@fx19.iad>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.18983.1424549962.18130.python-list@python.org>
Lines: 59
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:86066

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