As mentioned in the comments, this is comparable to finding a Hamiltonian path in a graph of tuple elements with directed edges between tuples with matching first and last elements. Although it is an NP-complete problem (the Hamiltonian path, I don't know if a different approach to your problem could make it easier), it is easy to come up with brute-force algorithms for it. This is a rather naive recursive implementation:
def chained_list(lst):
# List of rearranged elements
chain = []
# Flags to tell whether each item has been picked already
picked = [False] * len(lst)
# Loop to add all possible first elements (so the recursive function
# can work on the assumption that there is a previous element)
for i, item in enumerate(lst):
# Add first element
chain.append(item)
# Mark as picked
picked[i] = True
# Attempt recursion
_chain_list_rec(lst, picked, chain)
# If we got a rearranged list finish
if len(chain) == len(lst):
return chain
# Otherwise remove the selected first element
picked[i] = False
chain.pop()
raise ValueError('cannot chain list')
def _chain_list_rec(lst, picked, chain):
# Take previous value to match
_, prev = chain[-1]
# Iterate through items
for i, (item, p) in enumerate(zip(lst, picked)):
# If item is available and matches previous value
if not p and item[0] == prev:
# Add it and mark it as picked
chain.append(item)
picked[i] = True
# Try remaining recursion
_chain_list_rec(lst, picked, chain)
# Check if we finished
if len(chain) == len(lst):
return
# Undo adding if not finished
picked[i] = False
chain.pop()
print(chained_list([(5, 2), (3, 5), (3, 3), (1, 3)]))
# [(1, 3), (3, 3), (3, 5), (5, 2)]
print(chained_list([(5, 2), (3, 3), (1, 3)]))
# ValueError: cannot chain list
You can try to improve it in different ways, for example using a multiset instead of the list and a picked list of flags (assuming you want to support repeated elements, otherwise a set could do), using other data structures to search more quickly for the next potential item in the chain (e.g. a dict with key the first element and value a multiset of tuples starting with that element), or adding finish checks (check len(chain) == len(lst) at the beginning of the recursion to save the loop in the very last step). You can also check for feasibility of the current partial solution at every step in the recursion. Note that, for any partial solution: a) there must be at least one item starting with prev (the second value of the last item in chain) b) for any given value k, the number of available tuples starting with k must generally be equal to the number of available tuples ending with k, adjusting for k == prev and noting that there can be at most one k where there is an extra tuple finishing with k (which would be the last one). If these conditions don't hold, then that recursive path is not be feasible. You may think of other ways to improve the efficiency. In any case, however, the algorithm will become impossibly expensive to execute at one point or another, so keep in mind that this approach will only work for relatively small inputs.
