CODEWITHSUNDEEP
pythonlistmerge
Christophe Saugé
Christophe Saugé

Reputation: 41

How merge prev/next lists in python?

I have lists of exactly two previous and next items. 

[['Robert','Christopher'],['John','Eric'],['Mark','John'],['Mickael','Robert']]

For the first list, 'Robert' is previous and 'Christopher' next.

I would like to merge them having the lowest previous and the highest next by keeping the continuity of the final lists. Result can be:

[['Mickael','Christopher'],['Mark','Eric']]

or

[['Mark','Eric'],['Mickael','Christopher']]

The result is two lists because there are no continuity between these two lists. previous and next cannot be sorted (For example 'Mickael' is before 'Christopher'). There are no loops and no repeated elements (i.e. 'Robert' is always before 'Christopher', 'John' is always before 'Eric'...) so this is a topological graph

Is it possible easily in python?

Upvotes: 3

Views: 112

Answers (2)

Enfenion
Enfenion

Reputation: 512

I think this will work, and be quite efficient:

items = [['A','B'], ['B','C'], ['C','E'], ['E','F'], ['F','G']]
nodes = dict(items)
changed = True
while changed:
    changed = False
    keys = nodes.keys()
    for prevEl in keys:
        if not prevEl in nodes: #may have been deleted
            continue
        nextEl = nodes[prevEl]
        if nextEl in nodes:
            tmp = nodes[nextEl]
            del nodes[nextEl]
            nodes[prevEl] = tmp
            changed = True

Upvotes: 1

Christophe Saugé
Christophe Saugé

Reputation: 41

Based on How can I order a list of connections Ashwini Chaudhary's link (thx Ashwini), i have written a solution which fits my needs:

items= [['F','G'], ['B','C'], ['A','B'], ['C','D'], ['E','F']]
mydict = dict(items)
for prev,next in items:
    if next in mydict:
        mydict[prev] = mydict[next]
        del mydict[next]
print(list(mydict.items()))

Result is:

[('A', 'D'), ('E', 'G')]

Upvotes: 0

Related Questions