clever programming solution wanted
David Eppstein
eppstein at ics.uci.edu
Fri Jul 16 00:57:22 CEST 2004
In article <NY2dnS5S670Vm2rdRVn-uA at comcast.com>,
"Larry Bates" <lbates at swamisoft.com> 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" <sar38 at pantheon.yale.edu> wrote in message
> news:Pine.LNX.4.44.0407151728020.7818-100000 at ajax.its.yale.edu...
> > 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
More information about the Python-list
mailing list