algorizm to merge nodes

JD Jiandong.Ge at gmail.com
Fri Oct 17 23:34:28 CEST 2008


Hi,

Thanks,

It works for this example,

but if I add another item ['e', 'd']:
[['a', 'b'], \
     ['c', 'd'], \
     ['e', 'f'], \
     ['a', 'g'], \
     ['e', 'k'], \
     ['c', 'u'], \
     ['b', 'p'],\
     ['e', 'd']]

The result is
set(['a', 'p', 'b', 'g']), set(['e', 'c', 'u', 'd']), set(['k', 'e',
'd', 'f'])

The right result should be:

['a', 'p', 'b', 'g'], ['c', 'u', 'e', 'd', 'k', 'f']

JD




On Oct 17, 3:00 pm, Mensanator <mensana... at aol.com> wrote:
> On Oct 17, 3:20 pm, JD <Jiandong... at gmail.com> wrote:
>
>
>
> > Hi,
>
> > I need help for a task looks very simple:
>
> > I got a python list like:
>
> > [['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c',
> > 'u'], ['b', 'p']]
>
> > Each item in the list need to be merged.
>
> > For example, 'a', 'b' will be merged, 'c', 'd' will be merged.
>
> > Also if the node in the list share the same name, all these nodes need
> > be merged.
>
> > For example, ['a', 'b'], ['a', 'g'] ['b', 'p'] will be merged to ['a',
> > 'b', 'g', 'p']
>
> > The answer should be:
>
> > [['a', 'b', 'g', 'p'], ['c', 'd', 'u'], ['e', 'f', 'k']]
>
> > Anyone has a solution?
>
> A = [['a', 'b'], \
>      ['c', 'd'], \
>      ['e', 'f'], \
>      ['a', 'g'], \
>      ['e', 'k'], \
>      ['c', 'u'], \
>      ['b', 'p']]
>
> merged = []
>
> for i in A:
>     if len(merged)==0:
>         merged.append(set(i))
>     else:
>         gotit = False
>         for k,j in enumerate(merged):
>             u = j.intersection(set(i))
>             if len(u):
>                 merged[k] = j.union(set(i))
>                 gotit = True
>         if not gotit:
>             merged.append(set(i))
>
> print merged
>
> ##
> ##    [set(['a', 'p', 'b', 'g']), set(['c', 'u', 'd']), set(['k', 'e',
> 'f'])]
> ##
>
>
>
> > Thanks,
>
> > JD




More information about the Python-list mailing list