python re-arrange elements in a list based on the sublist values

Question

I have have a list of lists that I would like to re-arrange based on the values of its sublist.

list = [["c","d"], ["b", "c"], ["a", "b"], ["x", "y"]]

The final product should look like this:

new_list = [["a", "b"], ["b", "c"], ["c", "d"], ["x", "y"]]

The Python code should analyze each of the elements in list and re-arrange them into a new_list. Sublist with the same element should be placed side-by-side, for example ["b", "c"] should be placed after ["a", "b"] forming a chain of ["a", "b"], ["b", "c"].

Here is my attempt at getting the list sorted:

for i in list:
  if len(new_list) == 0:
    new_list.append(i)
  else:
    for j in new_list:
      if j[0] == i[1]:
        newindex = new_list.index(j)
        new_list.insert(newindex, i)

Unfortunely, with the above code I am getting an infinite loop which is stuck at the else block.

Any suggestions on a better solution is most welcomed. Thank you.

Answer 1

Based on @Adam.Er8 comment (I had the same idea, but his example is better than mine):

>>> L = [["b","m"], ["b","x"], ["b", "c"], ["a", "b"], ["x", "y"], ["m", "n"]]

The result is a forest. The idea is to build the trees from bottom to up, with a dict child -> parent:

>>> d = {}
>>> for u, v in L:
...     d[v] = u
...     if not u in d.keys():
...         d[u] = None
>>> d
{'m': 'b', 'b': 'a', 'x': 'b', 'c': 'b', 'a': None, 'y': 'x', 'n': 'm'}

Now, it's easy to reverse the trees:

>>> e = {}
>>> for k, v in d.items():
...     e.setdefault(v, []).append(k)
>>> e
{'b': ['m', 'x', 'c'], 'a': ['b'], None: ['a'], 'x': ['y'], 'm': ['n']}

With a DFS, you can output the paths:

>>> def dfs(x, stack=[]):
...     if x in e:
...         for y in e[x]:
...             yield from dfs(y, stack + [x])
...     else:
...         yield stack + [x]

>>> P = list(dfs(None))
>>> P
[[None, 'a', 'b', 'm', 'n'], [None, 'a', 'b', 'x', 'y'], [None, 'a', 'b', 'c']]

And finally:

>>> for p in P:
...     print(list(zip(p[1:], p[2:])))
[('a', 'b'), ('b', 'm'), ('m', 'n')]
[('a', 'b'), ('b', 'x'), ('x', 'y')]
[('a', 'b'), ('b', 'c')]