Chain last element of list with equal first element of another list

Question

this has had me occupied half of the afternoon already... I am trying to chain the last and first elements of a nested list. I'll illustrate this with an easy example:

input = [(8, 2), (8, 5), (2, 12), (12, 13), (5, 6), (6, 7), (13, 14), 
         (14, 3), (7, 4), (3, 4)]
result = [(8, 2), (2, 12), (12, 13), (13, 14), (14, 3), (3, 4), (4, 7),
          (7, 6), (6, 5), (5, 8)]

I have tried the following code:

def ChainNew(L):
    R = copy.deepcopy(L)
    for pair in R:
        pair.reverse()
    stop = len(L)
    chain = [L.pop(0)]
    L = sorted(L)
    R = sorted(R)
    while len(chain) < stop:
        for i, j in zip(L, R):
            if i[0] == chain[len(chain)-1][1]:
                chain.append((i))
                L.remove(i)
                R.remove(i[::-1])
                break
            if j[0] == chain[len(chain)-1][1]:
                chain.append((j))
                L.remove(j[::-1])
                R.remove(j)
                break
    return chain

but not only is this inefficient, but it also is buggy: it doesn't seem to return all elements of the initial list. For example:

L =  [[20, 56], [23, 24], [23, 12], [22, 21], [26, 48], [26, 24],
      [55, 48], [55, 39], [56, 40], [19, 6], [19, 12], [6, 15],
      [40, 39], [21, 57], [14, 15], [14, 16], [57, 50], [45, 9],
      [45, 53], [18, 42], [18, 9], [38, 53], [38, 44], [50, 42],
      [16, 17], [17, 35], [36, 37], [36, 35], [37, 44]]

return = [[20, 56], [56, 40], [40, 39], [39, 55], [55, 48], [48, 26],
          [26, 24], [24, 23], [23, 12], [12, 19], [19, 6], [6, 15], 
          [15, 14], [14, 16], [16, 17], [17, 35], [35, 36], [36, 37], 
          [37, 44], [44, 38], [38, 53], [53, 45], [45, 9], [9, 18], 
          [18, 42], [42, 50], [50, 57]]

There must be an easier way of doing this...

EDIT: sorry! I forgot to mention that the the integers inside each list (pair) can be swapped. For example (7, 4) to (4, 7).

Basically what I have here in each pair of numbers are the indexes of an edge of a polyline. All the edges together form the polyline. So by "chaining" each pair of numbers, I can get the indexes of the vertices of a polyline in a sorted manner.

EDIT AGAIN: The correct result of the list L would be:

return = [[22, 21], [21, 57], [57, 50], [50, 42], [42, 18], [18, 9],
          [9, 45], [45, 53], [53, 38], [38, 44], [44, 37], [37, 36],
          [36, 35], [35, 17], [17, 16], [16, 14], [14, 15], [15, 6],
          [6, 19], [19, 12], [12, 23], [23, 24], [24, 26], [26, 48],
          [48, 55], [55, 39], [39, 40], [40, 56], [56, 20]]

Thanks!

Answer 1

How about:

def path(a, b):
    if not b:
        return a
    for n, (p, q) in enumerate(b):
        if p == a[-1][1]:
            return path(a + [(p, q)], b[:n] + b[n+1:])
        if q == a[-1][1]:
            return path(a + [(q, p)], b[:n] + b[n+1:])
    raise ValueError("no path", a, b)

L = [(8, 2), (8, 5), (2, 12), (12, 13), (5, 6), (6, 7), (13, 14), (14, 3), (7, 4), (3, 4)]
print path([L[0]], L[1:])
#[(8, 2), (2, 12), (12, 13), (13, 14), (14, 3), (3, 4), (4, 7), (7, 6), (6, 5), (5, 8)]

Answer 2

Here's a solution that finds all possible chains:

def find_chains(points):
    """For a list of points, take the first point and finds all chains that
    could be made from the following points.

    Returns a list of lists of tuples. Each sublist is a possible chain.
    """

    def find_solutions(start, choices):
        """For a starting point and a list of choices, return all choices that
        might succeed that point.

        Returns a list of tuples. These tuples contain the next choice, and all
        of the remaining points should that choice be used.
        """

        ret = []
        for i, possible_choice in enumerate(choices):
            # Determine whether or not the choice is appropriate.
            added_choice = None
            if start[1] == possible_choice[0]:
                added_choice = possible_choice
            elif start[1] == possible_choice[-1]:
                added_choice = possible_choice[::-1]

            # If it is, add a tuple of that choice and all other choices to the
            # return list.
            if added_choice:
                ret.append((
                    added_choice,
                    [
                        k
                        for j, k
                        in enumerate(choices)
                        if i != j
                    ]
                ))

        return ret

    solutions = []
    start = points[0]
    other_points = points[1:]
    if not other_points:
        # If there aren't any remaining points, then the only possible path is
        # that of just the first point.
        return [[start]]

    # Find all chains through `other_points` and add them to our solutions.
    for next_point, remaining_points in find_solutions(start, other_points):
        for subchain in find_chains([next_point] + remaining_points):
            solutions.append([start] + subchain)
    return solutions

The difference between this solution and other, shorter solutions is that the others just take the first possible point and find the subchain from there, whereas this one takes every possible point. Example:

test = [(1, 2), (2, 3), (2, 4), (3, 4)]
print(find_chains(test))
# Finds two possible solutions:
# [[(1, 2), (2, 3), (3, 4), (4, 2)],
#  [(1, 2), (2, 4), (4, 3), (3, 2)]]

test = [(8, 2), (8, 5), (2, 12), (12, 13), (5, 6), (6, 7), (13, 14),
        (14, 3), (7, 4), (3, 4)]
print(find_chains(test))
# Finds the only solution:
# [[(8, 2), (2, 12), (12, 13), (13, 14), (14, 3), (3, 4), (4, 7), (7, 6), (6, 5), (5, 8)]]

test = [(1, 2), (3, 4)]
print(find_chains(test))
# There weren't any solutions:
# []