Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > clever programming solution wanted

Reply
Thread Tools

clever programming solution wanted

 
 
Scott Rifkin
Guest
Posts: n/a
 
      07-15-2004
If anyone has a good, quick solution to the following in python2.3
I'd appreciate it:

I have a dictionary with keys K1, K2, ..., K10000
Each entry looks like:

dict[K1]=[T1,T4,T500]

where the T's are indexed from, say, 1 to 20000 and each K has some number
of Ts (not always 3).

I want to create groups of Ks which share Ts such the groups are maximal,
for instance:

dict[K1]=[T1,T4,T500]
dict[K2]=[T1]
dict[K3]=[T500,T7000]

these would be grouped [K1,K2,K3].

At the end, most of the Ks will be by themselves, but some will be grouped
with some number of other Ks.


Thanks for any help,

Scott Rifkin

scott dot rifkin at yale dot edu


 
Reply With Quote
 
 
 
 
Larry Bates
Guest
Posts: n/a
 
      07-15-2004
Maybe someone else can decipher this. I just don't
know what "such that the groups are maximal" could
possibly mean.

Larry Bates

"Scott Rifkin" <(E-Mail Removed)> wrote in message
news(E-Mail Removed)...
> If anyone has a good, quick solution to the following in python2.3
> I'd appreciate it:
>
> I have a dictionary with keys K1, K2, ..., K10000
> Each entry looks like:
>
> dict[K1]=[T1,T4,T500]
>
> where the T's are indexed from, say, 1 to 20000 and each K has some number
> of Ts (not always 3).
>
> I want to create groups of Ks which share Ts such the groups are maximal,
> for instance:
>
> dict[K1]=[T1,T4,T500]
> dict[K2]=[T1]
> dict[K3]=[T500,T7000]
>
> these would be grouped [K1,K2,K3].
>
> At the end, most of the Ks will be by themselves, but some will be grouped
> with some number of other Ks.
>
>
> Thanks for any help,
>
> Scott Rifkin
>
> scott dot rifkin at yale dot edu
>
>



 
Reply With Quote
 
 
 
 
Jeff Epler
Guest
Posts: n/a
 
      07-15-2004
It sounds to me like you have a somewhat odd representation of an
undirected graph and you want to find connected components.

http://www.cs.sunysb.edu/~algorith/files/dfs-bfs.shtml
http://www.csee.usf.edu/~maurer/graphs/sld024.htm
etc

In an edge-list representation, I think the solution looks something
like (untested):
all_components = []
while input:
initial_element = input.pop()
visit = [initial_element]
component = Set([initial_element])
while visit:
v = visit.pop()
vs = neighbors[v] - component:
component |= vs
visit.extend(vs)
all_components.append(component)
input -= component
This is a O(V+E) algorithm unless I messed something up.

Converting from your d[Ki] = [Tj, Tk, ...] to edge-list representation
is probably O(V^2). Something like (untested):
neighbors = dict([(v, Set()) for v in d])
ds = dict([(k, Set(v)) for k, v in d.iteritems()])
for v1 in d:
for v2 in d:
if ds[v1] & ds[v2]:
neighbors[v1].add(v2)
neighbors[v2].add(v1)

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFA9wsdJd01MZaTXX0RAlLiAJ0W0EAqyLnZMffTsenA0/SDkIpivwCff0FN
TLB2hvR3Xb+bvhUWTMKHrMw=
=WNp+
-----END PGP SIGNATURE-----

 
Reply With Quote
 
David Eppstein
Guest
Posts: n/a
 
      07-15-2004
In article <(E-Mail Removed)>,
"Larry Bates" <(E-Mail Removed)> wrote:

> Maybe someone else can decipher this. I just don't
> know what "such that the groups are maximal" could
> possibly mean.
>
> Larry Bates
>
> "Scott Rifkin" <(E-Mail Removed)> wrote in message
> news(E-Mail Removed)...
> > If anyone has a good, quick solution to the following in python2.3
> > I'd appreciate it:
> >
> > I have a dictionary with keys K1, K2, ..., K10000
> > Each entry looks like:
> >
> > dict[K1]=[T1,T4,T500]
> >
> > where the T's are indexed from, say, 1 to 20000 and each K has some number
> > of Ts (not always 3).
> >
> > I want to create groups of Ks which share Ts such the groups are maximal,
> > for instance:
> >
> > dict[K1]=[T1,T4,T500]
> > dict[K2]=[T1]
> > dict[K3]=[T500,T7000]


The way I interpreted it: draw an undirected bipartite graph from the
K's to the T's, find connected components, and report the K's in each
connected component.

Something like:

from sets import Set

def keygroups(dictKT):
dictTK = {}
for k,tlist in dictKT.iteritems():
for t in tlist:
dictTK.setdefault(t,[]).append(k)
visitedK = Set()
visitedT = Set()
for k in dictKT:
if k not in visitedK:
component = Set([k])
unexplored = [k]
while unexplored:
k = unexplored.pop()
component.add(k)
for t in dictKT[k]:
if t not in visitedT:
visitedT.add(t)
for k in dictTK[t]:
if k not in visitedK:
visitedK.add(k)
unexplored.append(k)
yield list(component)

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Typed Datasets and ObjectDataSource - clever solution to the scalarparameters problem? JimLad ASP .Net 3 11-30-2009 11:18 AM
looking for a clever preprocesser solution Mark P C++ 4 12-22-2005 10:36 AM
HELP WANTED HELP WANTED HELP WANTED Harvey ASP .Net 1 07-16-2004 01:12 PM
HELP WANTED HELP WANTED HELP WANTED Harvey ASP .Net 0 07-16-2004 10:00 AM
Is there any clever solution? A Python 0 07-14-2003 08:10 PM



Advertisments