Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Sat, 21 Feb 2015 12:11:12 -0800
From: Ethan Furman <ethan@stoneleaf.us>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.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: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="hDpQf0vmvWg4tAnd60rCg4Wb1VvkTa39s"
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.18982.1424549507.18130.python-list@python.org>
Lines: 73
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:86065

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--hDpQf0vmvWg4tAnd60rCg4Wb1VvkTa39s
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

On 02/21/2015 11:46 AM, TommyVee wrote:
> Start off with sets of elements as follows:
>=20
> 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
>=20
> Note that sets 1, 3 and 4 all have the element 'E' in common, therefore=
 they are "related" and form the following superset:
>=20
> A,B,C,D,E,F,X,Z
>=20
> 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:
>=20
> G,H,L,M,O,P,Q,R,Y
>=20
> I think you get the point.  As long as sets have at least 1 common elem=
ent, 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).=20
> Cycles thankfully, are not possible.
>=20
> BTW, the number of individual sets (and resultant supersets) will be ve=
ry large.
>=20
> I don't know where to start with this.  I thought about some type of re=
cursive algorithm, but I'm not sure.  I could
> figure out the Python implementation easy enough, I'm just stumped on t=
he algorithm itself.
>=20
> Anybody have an idea?

Use a Counter (collections.Counter), add all sets, then keep any keys wit=
h a count of 2 or more.

--
~Ethan~


--hDpQf0vmvWg4tAnd60rCg4Wb1VvkTa39s
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQIcBAEBAgAGBQJU6OZgAAoJENZ7D1rrH75N+CwQAL7HBkDIrNBD+pQh55urq/s0
saudNun4Rn7ZyOaKncokJ2hfJdIETPA7RXGmrd/5+RPe5eqRTRXW9l/7yxAjzUHt
axLHOjfZx2CuNSor7nkUGf7oQgw0SvuNrmQJCTAvmWjlkuYtcx8JJXqcMpbI6F5k
bS2Lx5SwmJv3eqTUmttSIzw6w8Z0p9fidGJh5ZgwkF+59IgzHnjr/TWV5mb8CRtg
eJnCXyqtfYmkAQfH8Bx9MeEq7eBGHl/95TRMBZteRNzPoWnClZHAcVLtULUdvOWx
HnZ0SyUFNiYq5e1vGhHyA6B/Gp9lHME53pj2aIjKBzfUuvrm+JqarHmFuTBSqm4S
KGm2Unj9Nsla8YAOTWVhC0HJiC1cUh2xLKSqbdthvvw2MpTau2TNVPmBaSVyVmdA
UCuZtFWKWBREEz68OjFUI4jQAWO8tp1f3GrIbT67KhXTx7vrA756SWD000nxqmnt
b6QM0dN34oSQe8+pR/mgh+gdLY5/syYHRa43qvLjMuR+hKkZSdrR/ddD3CgCIOYa
ZmFN1W++Szc4JrrUh6tY4JF93t7lBGjGAB4rXR0Qi9+hHfsjiE09Wj0eLIU5QpWp
hJqUAW0NATKgkTDUIcNpa+ac+boWrUVFNoyss94yZrj8ENPkyGLUA/gqZui+mJfZ
gOBcJBestrW5tu1p4DRB
=L14i
-----END PGP SIGNATURE-----

--hDpQf0vmvWg4tAnd60rCg4Wb1VvkTa39s--