Sort list of tuples based on unique occurrence from beginning to end

Question

Let's say I have a list of tuples like:

x = [(2, 18), (18, 5), (3, 2)]

How can I sort this list of tuples based on the unique occurrence of the values in the tuples?

For example, since the number 3 only occurs in the tuple (3, 2) and is the first value of the tuple, it should be the first entry in the list. This entry is followed by (2, 18) because the second value (2) of (3, 2) occurs in the first value of (2, 18). And finally, the last entry in the list should be (18, 5), since its first value matches the last value of (2, 18).

Expected result:

[(3, 2), (2, 18), (18, 5)]

Pls tell me if you need more info.

so basically like [dominoes](https://en.wikipedia.org/wiki/Dominoes)? — Matiiss, Mar 17 '22 at 09:05
Oh ya! Good point. Yes like dominoes, did not think of it like that. I can close the question if you point me to some post — , Mar 17 '22 at 09:06
seems like a pretty good question, except you haven't provided your solution (a [mre]), but also it wouldn't exactly be sorting? similar but really you are finding matching numbers and placing them adjacent to each other which is kind of its own algorithm, probably someone has already done it but unfortunately I don't currently have any sources for that — Matiiss, Mar 17 '22 at 09:09
Does this answer your question? [Sort a list of two-sided items based on the similarity of consecutive items](https://stackoverflow.com/questions/49037391/sort-a-list-of-two-sided-items-based-on-the-similarity-of-consecutive-items) — Matiiss, Mar 17 '22 at 09:11
Off the top of my head, this feels like a [topological sort](https://en.wikipedia.org/wiki/Topological_sorting). — Ture Pålsson, Mar 17 '22 at 09:14
@Matiiss did you check the answer you linked? I do not think it is what I am looking for — , Mar 17 '22 at 10:18
well, it seemed alright at a quick glance, one of the answers even uses the word _domino_... and it kind of works okay... probably some tweaking and should work as expected, for example it correctly sorts this list: `[(2, 18), (6, 3), (18, 5), (3, 2), (5, 6)]` — Matiiss, Mar 17 '22 at 10:24

score 0 · Accepted Answer · answered Mar 17 '22 at 10:40

Use a recursive function to pick dominos one by one:

def get_elements_filtered_by_first_values(original_list, first_value):
   return [each_element for each_element in original_list if each_element[0] == first_value]

def add_next_domino(list_of_remained_dominos, list_of_picked_dominos):
   possible_domino_list_to_pick = get_elements_filtered_by_first_values(list_of_remained_dominos, list_of_picked_dominos[-1][1])
   if not len(possible_domino_list_to_pick):
      return None
   for each_possible_domino_to_pick in possible_domino_list_to_pick:
      new_list_of_picked_dominos = list_of_picked_dominos + [each_possible_domino_to_pick]
      new_list_of_remained_dominos = list_of_remained_dominos[:]
      new_list_of_remained_dominos.remove(each_possible_domino_to_pick)
      if not len(new_list_of_remained_dominos):
         return new_list_of_picked_dominos
      pick_domino_result = add_next_domino(new_list_of_remained_dominos, new_list_of_picked_dominos)
      if pick_domino_result is not None:
         return pick_domino_result
   return None

x = [(2, 18), (18, 5), (3, 2)]
eligible_elements = [each_element for each_element in x if each_element[0] not in map(lambda x: x[1], x)]
while len(eligible_elements):
   next_eligible_element = eligible_elements.pop()
   return_list = add_next_domino([each_element for each_element in x if each_element != next_eligible_element] ,[next_eligible_element])
   if return_list is not None:
      print(return_list)
      break

The output:

[(3, 2), (2, 18), (18, 5)]

Sort list of tuples based on unique occurrence from beginning to end

1 Answers1