Reordering a list of tuples to match the value of the next element in the list

Question

If I have a list of tuples like this [(1, 3), (-6, 3), (1, 7)] and i would like to return a list like this [(7, 1),(1, 3), (3, -6)]. What can I do?, any ideas on how to sort the tuples. The essential condition is based on the fact that they "connect" by having the same value as the starting value in the next tuple.

I tried this code where I tried to place everything into a graph (adjacency list/dict) where each key is an element of the tuples and then i tried to arrange it following the conditions I mentioned previously but it is not working correctly. With inputs like the one given previously

list = [(1, 3), (-6, 3), (1, 7)]

the output was [(1, 3), (3, 7), (7, -6)]

instead of [(7, 1),(1, 3), (3, -6)]

this is the code i used

def compoundGraph(compounds):
    graph = {}
    for tuple in compounds:
        if tuple[0] in graph:
            graph[tuple[0]].append(tuple[1])
        else:
            graph[tuple[0]] = [tuple[1]]
    return graph

def traverse(graph, start, visited, result):
    if start not in visited:
        visited.add(start)
        result.append(start)
        if start in graph:
            for neighbor in graph[start]:
                traverse(graph, neighbor, visited, result)

def reorderCompounds(tuples_list):
    graph = compoundGraph(tuples_list)
    result = []
    visited = set()
    keys_copy = list(graph.keys())
    for start in keys_copy:
        traverse(graph, start, visited, result)
    return [(result[i], result[i+1]) for i in range(len(result)-1)]

list = [(1, 3), (-6, 3), (1, 7)]
print(reorderCompounds(list))

If anyone has a more elegant or at least correct idea on how to tackle this problem, the help would be appreciated.

Answer 1

import networkx as nx

data = [(1, 2), (2, 3), (3, 4), (4, 1),
        (1, 5), (5, 6), (6, 7), (7, 1),
        (2, 6), (6, 8), (8, 9), (9, 2)]

#data  = [(1, 3), (-6, 3), (1, 7)]
G = nx.DiGraph()
G.add_edges_from(data)
print(G)#DiGraph with 9 nodes and 12 edges

# Check for Eulerian path 
if not nx.is_eulerian(G):
  print("No Eulerian path exists")
  exit()

# Use built-in function for finding an Eulerian circuit (if exists)
euleriancircuit = list(nx.eulerian_circuit(G))

# remove last element if it's a self-loop
if euleriancircuit[0] == euleriancircuit[-1]:
  euleriancircuit.pop()

print(euleriancircuit)
#[(1, 5), (5, 6), (6, 8), (8, 9), (9, 2), (2, 6), (6, 7), (7, 1), (1, 2), (2, 3), (3, 4), (4, 1)]

Answer 2

If you don't want to reinvent the wheel, one option could be to use the networkx library and eulerian_path:

import networkx as nx

edges = [(1, 3), (-6, 3), (1, 7)]

out = list(nx.eulerian_path(nx.from_edgelist(edges)))

Output:

[(-6, 3), (3, 1), (1, 7)]

Graph:

Answer 3

You can iteratate over the given edges and recursively yield paths where the starting vertice of the starting edge matches the ending vertice of the current edge in either direction:

def get_connected(edges):
    if not edges:
        yield []
    for i, edge in enumerate(edges):
        for path in get_connected(edges[:i] + edges[i + 1:]):
            for start, end in edge, reversed(edge):
                if not path or path[0][0] == end:
                    yield [(start, end)] + path

so that:

print(*get_connected([(1, 3), (-6, 3), (1, 7)]), sep='\n')

outputs:

[(-6, 3), (3, 1), (1, 7)]
[(7, 1), (1, 3), (3, -6)]

Demo: https://ideone.com/snVSQM

Answer 4

A solution for small lists

A simple Branch&Bound should be enough is list is not too big (Well, a recursive search. It is not really branch&bound, since there isn't really any strategy to cut some recursions)

l = [(1, 3), (-6, 3), (1, 7)] # btw, do not name variables "list". That a python predefined function


# Branch & bound
def bb(l, partial=[]):
    # if list of tuple we need to order is empty, then we have finished
    if l==[]: return partial
    # Otherwise, we need to try to continue our partial solution
    # with tuples (in any order)
    for i,(x,y) in enumerate(l):
        # Try to add (x,y) to our partial solution, if this is the first 
        # tuple of that solution, or if x is the terminal value of last tuple
        # of solution
        if len(partial)==0 or x==partial[-1][1]:
            # Recursively try to place the rest
            r=bb(l[:i]+l[i+1:], partial+[(x,y)])
            # If we succeed, that our solution (you asked for just one, not all of them)
            if r: return r
            # If not, we must continue with other possibilities
        if len(partial)==0 or y==partial[-1][1]:
            r=bb(l[:i]+l[i+1:], partial+[(y,x)])
            if r: return r
    return False

Since it is recursive, it implicitly does some back tracking. Which may be necessary. A greedy algorithm is not always sufficient here. Think of (0,1), (1,2), (2, 1), (1,3), (3,4)
if you tried first to add (0,1)
then adding (1,3) to it (it fits) (0,1), (1,3)
then adding the only possibility (3,4)
(0,1), (1,3), (3,4)
and then you are stuck

Point is, backtracking is necessary.

For bigger list: this is euler's trail problem

If the list is bigger than that, the problem may become more complicated. What you are doing here is searching for an Eulerian chain into an undirected graph, whose nodes are numbers, and edges are the tuples.

Knowing if such a chain exist is easy. This has been solved by Euler centuries ago: you just need to count the number of occurrence of every numbers in the list. And if more than 2 numbers are seen an odd number of occurrences, then, there is no solution. If not, there is a solution.

Finding the eulerian chain (not just knowing that it exist) is a bit more complicated. My recursive search could be a method, but it dosn't take advantage of the fact that this is just an instance of Königsberg problem (the, problem of searching an Eulerian chain).

Choose starting point

For example, my algorithm could be improved by starting with a number that is seen an odd number of times in the list (we known that starting and ending point are those 2 numbers that are seen an odd number of time. Unless there isn't any, in which case, we know that the chain is a cycle: it doesn't matter where you start, and you'll end at the starting number)

from collections import Counter
def bb(l, partial=[]):
    # if list of tuple we need to order is empty, then we have finished
    if l==[]: return partial
    # Otherwise, we need to try to continue our partial solution
    # with tuples (in any order)
    # where to start:
    if len(partial):
        start=partial[-1][1] # start with last element in partial solution if any
    else:
        # start chain with odd occurrence number
        occ=Counter([x for (x,y) in l]+[y for (x,y) in l])
        odd=[k for k in occ if occ[k]%2]
        if len(odd)>0:
            start=odd[0]
        else:
            # all numbers appear an even number of time: we can start wherever
            # we want, there is a solution starting from everywhere
            start=l[0][0]
    for i,(x,y) in enumerate(l):
        # Try to add (x,y) to our partial solution, 
        if x==start:
            # Recursively try to place the rest
            r=bb(l[:i]+l[i+1:], partial+[(x,y)])
            # If we succeed, that our solution (you asked for just one, not all of them)
            if r: return r
            # If not, we must continue with other possibilities
        if y==start:
            r=bb(l[:i]+l[i+1:], partial+[(y,x)])
            if r: return r
    return False

other than this choice of starting point, the algorithm is the same as the first one. If there are only a few tuples in the list, then, cost of searching the starting point would exceed the cost of just trying them all (as my first algorithm does). But for a long enough list (especially if some numbers are repeated more than once, and if many backtracking is necessary), then avoiding whole useless branches by knowing at least where to start is already a serious improvement.

If you need better algorithm, search for Euler chain (or Euler path, or Euler trail). That is what you are trying to do. But that is not just a "how to sort tuples" problem. That is a quite complicated problem. With still some research paper nowadays about it (sure, it is also because it is the problem with which any graph-theory course starts that it is a famous playground for new algorithms).

You could try to adapt Hierholzer algorithm to your case (not really an adaptation. Since that is not "similar" to Euler path problem. It IS Euler path problem. Just, not with nodes and edges representation. So you would need to translate "edge" by "tuple" and "node" by "number" when reading algorithms)

Answer 5

You're on the right track man, but try this code out:

def compoundGraph(compounds):
    graph = {}
    for tuple in compounds:
        if tuple[0] in graph:
            graph[tuple[0]].append(tuple[1])
        else:
            graph[tuple[0]] = [tuple[1]]
    return graph

def traverse(graph, start, visited, result):
    if start not in visited:
        visited.add(start)
        if start in graph:
            for neighbor in sorted(graph[start], reverse=True):
                traverse(graph, neighbor, visited, result)
        result.append(start)

def reorderCompounds(tuples_list):
    graph = compoundGraph(tuples_list)
    result = []
    visited = set()
    for start in graph.keys():
        traverse(graph, start, visited, result)
    return [(result[i+1], result[i]) for i in range(len(result)-1)]

# Test the function with your example
input_list = [(1, 3), (-6, 3), (1, 7)]
print(reorderCompounds(input_list))