algorizm to merge nodes

[JD]

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?

Thanks,

JD

 

[Chris Rebert]

(Disclaimer: completely untested)

from collections import defaultdict

merged = defaultdict(list)
for key, val in your_list_of_pairs:
merged[key].append(val)

result = [[key]+vals for key, vals in merged.items()]

Cheers,
Chris

 

[JD]

Hi,

Thanks for the help,

but the result is not quite right:

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

the ['b', 'p'] is not merged.

JD

(Disclaimer: completely untested)

from collections import defaultdict

merged = defaultdict(list)
for key, val in your_list_of_pairs:
merged[key].append(val)

result = [[key]+vals for key, vals in merged.items()]

Cheers,
Chris
--
Follow the path of the Iguana...http://rebertia.com

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?

JD

 

[Mensanator]

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'])]
##

 

[bearophileHUGS]

JD, you probably need the algorithm for connected components of an
undirected graph.

For example you can do that with my graph lib:
http://sourceforge.net/projects/pynetwork/

from graph import Graph
g = Graph()
data = [['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'],
['c', 'u'], ['b', 'p']]
g.addArcs(data, bi=True)

print g.connectedComponents()
# Output: [['a', 'b', 'g', 'p'], ['c', 'u', 'd'], ['e', 'k', 'f']]

Bye,
bearophile

 

[JD]

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

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

 

[JD]

Thanks,

This one really works.

JD

 

[Paul McGuire]

Hi,

I need help for a task looks very simple:

<snip>

I smell "homework assignment".

-- Paul

 

[Mensanator]

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

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']]

Well, you should have asked for that, if that's what you wanted.

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

A.sort()

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'])]
##

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

 

[Gerard flanagan]

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?

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


def merge(inlist):
n = len(inlist)
outlist = [set(inlist.pop())]
while inlist:
s = set(inlist.pop())
merged = False
for i in range(len(outlist)):
t = outlist
u = s | t
if len(u) < len(s) + len(t):
outlist = u
merged = True
break
if not merged:
outlist.append(s)
if len(outlist) == n:
return outlist
else:
return merge(outlist)

for s in merge(data):
print s

 

[JD]

It could be a very good "homework assignmet".

This is for a real application.

each item in the list represent two terminals of a resistor. All the
resistors in the list are shorted, I need to figure out how many
independent nets are there.

JD

 

[bearophileHUGS]

JD:

Thanks,
This one really works.

Note that you can save some RAM (almost half) creating a directed
graph, because later the connectedComponents() manages the arcs as
undirected anyway:

from graph import Graph
g = Graph()
data = [['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'], ['e', 'k'], ['c', 'u'], ['b', 'p']]
g.addArcs(data)
g.connectedComponents()

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

Bye,
bearophile