How merge prev/next lists in python?

Question

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?

Related: http://stackoverflow.com/questions/16409486/how-can-i-order-a-list-of-connections — Ashwini Chaudhary, May 07 '13 at 09:53
You are basically looking for the start and end points for possible paths through a graph here. — Martijn Pieters, May 07 '13 at 09:58
Do you've loops in your data, for example : `[A,B], [B,A], [C,D]`? this will result in (A,A), (C,D). — Ashwini Chaudhary, May 07 '13 at 10:40
No i will not have loops. 'A' will always be before than 'B', 'B' before than 'C'... Nevertheless, I can have different orders for these couples: [B,C], [A,B], [C,D], [F,G], [E,F] — Christophe Saugé, May 07 '13 at 10:44
@ChristopheSaugé Then see the solutions on the link I posted earlier. — Ashwini Chaudhary, May 07 '13 at 10:45
This is a kind of solution but i do not have any loops as the link refers to. The solution could be simpler i think (use of dictionary seems useless) — Christophe Saugé, May 07 '13 at 10:56
@ChristopheSaugé Your question is a graph related problem, for finding paths dicts are going to be the most appropriate data structures here. And my [solution](http://stackoverflow.com/a/16409770/846892) on that page works fine for your question. — Ashwini Chaudhary, May 07 '13 at 11:09

Enfenion · Answer 1 · 2013-05-07T14:47:46.783

1

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

edited May 07 '13 at 14:47

answered May 07 '13 at 10:04

Enfenion

502
3
8

It does not work with: items= [['F','G'], ['B','C'], ['A','B'], ['C','D'], ['E','F']] – Christophe Saugé May 07 '13 at 10:46
items cannot be sorted. I will edit my topic to be more clear. – Christophe Saugé May 07 '13 at 11:00
Can you have repeated elements? For example: items = [['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'D'] – Enfenion May 07 '13 at 11:59
I'm not allowed to comment on the answer below, but it gives the wrong answer for [['G','D'], ['E','F'], ['F','G']]. It gives [('A', 'D'), ('E', 'G')] instead of [('E', 'D')]. – Enfenion May 07 '13 at 14:40

score 0 · Accepted Answer · edited May 23 '17 at 12:03

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

How merge prev/next lists in python?

2 Answers2