Sort a list of start and end points strings

I am trying to solve a simple problem in python but i'm really struggling.

I have a list of strings that looks like this:

["1->5","2->4","5->3","3->2"]

where the first number before the arrow represents the start point and the number after the finish point. Either string in the list represents one movement, (1->5 started from 1 and went to 5)

The goal is to create a single line that resume all the list. In the example above, the output would be:

1 -> 5 -> 3 -> 2 -> 4

which is the "full movement"

Convert it to a graph, then record your traversal of the graph:

# Make a graph:
lst = ["1->5","2->4","5->3","3->2"]
graph = {move.split("->")[0]: move.split("->")[1] for move in lst}  # {'1': '5', '2': '4', '5': '3', '3': '2'}

# Traverse graph:
start = "1"  # Starting point
result= [int(start)]
val = graph[start]
while val:
    result.append(int(val))  # I assume you want integers.
    val = graph.get(val)

print(result)  # [1, 5, 3, 2, 4]

This code converts your list to the graph {'1': '5', '2': '4', '5': '3', '3': '2'} using a dict comprehension, and then traverses it while recording the path it took in result. You can change the start variable to wherever you'd like to start.

Another option:

strings = ["1->5", "2->4", "5->3", "3->2"]
moves = dict(string.split("->") for string in reversed(strings))
stations = list(moves.popitem())
while end := moves.pop(stations[-1], False):
    stations.append(end)
result = " -> ".join(stations)  # For the sample: '1 -> 5 -> 3 -> 2 -> 4' 

Transform the splitted strings into a dictionary moves, in reversed order. Pop the last key-value tuple (from the first string) and make a list stations out of it. Then go through the moves as long as possible.

Something like this?

# Your list
l = ["1->5","2->4","5->3","3->2"]

# Create a dictionary of your pairs
dct = {int(i[0]) : int(i[1]) for i in [i.split("->") for i in l]}
# {1: 5, 2: 4, 5: 3, 3: 2}

# This will contain the result.
new_list = []

# Manually set the last stop to the first int of the first pair.
last_stop = int(l[0].split("->")[0])

# and add it to the new_list
new_list.append(last_stop)

# Iterate for (len(l)), finding the value for the last stop, and add it to new_list. 
for i in range(len(l)):
    next_value = dct[last_stop]
    new_list.append(next_value)
    last_stop = next_value

print(new_list)
# [1, 5, 3, 2, 4]

</details>



# 答案4
**得分**: 0

你可以通过在一个遍历中保持部分连接的链路并使用两个字典来追踪它们来一次性连接路径。一个字典用于索引链条的第一个数字，另一个用于通过它们的最后一个数字来索引链条。在遍历每个链接以将子链连接在一起后，最后连接的链条应该包含所有的链接。

links = ["1->5","2->4","5->3","3->2"]

starts = dict() # 以链条的第一个数字为索引
ends = dict() # 以相同链条的最后一个数字为索引
for link in links:
s,e = link.split("->") # 链接的起始和结束
chain = ends.pop(s,

print(*chain,sep="->") # 最后一个链条就是结果

1->5->3->2->4

或者，你可以使用一个字典将每个数字映射到下一个数字。然后，通过使用集合差异（起始数字和结束数字之间的差异）来找到起始点。链路链可以通过在字典中按照下一个数字一直跟踪直到没有下一个数字（在链条的最后一个条目）为止来组装：

links = ["1->5","2->4","5->3","3->2"]

nextNum = dict(link.split("->") for link in links) # 映射到下一个数字
chain = list(set(nextNum)-set(nextNum.values()))[:1] # 第一个数字
chain.extend(filter(None,map(nextNum.get,chain))) # 跟随链接直到结束

print(*chain,sep="->")

1->5->3->2->4

<details>
<summary>英文:</summary>

You could link the path in one pass by keeping track of partially linked chains in two dictionaries.  One that indexes the first number in a chain and one to index the chains by their last number. After going through each links to connect sub-chains together, the last chain connected should have all the links together. 

    links  = [&quot;1-&gt;5&quot;,&quot;2-&gt;4&quot;,&quot;5-&gt;3&quot;,&quot;3-&gt;2&quot;]
    
    starts = dict() # index on first number of chain
    ends   = dict() # index on last number of same chains
    for link in links:
        s,e = link.split(&quot;-&gt;&quot;)                       # start and end of link 
        chain  = ends.pop(s,
展开收缩
) + starts.pop(e,[e]) # link 2 chains
        starts[chain[0]] = ends[chain[-1]] = chain   # update indexing

    print(*chain,sep=&quot;-&gt;&quot;) # last chain is the result
    # 1-&gt;5-&gt;3-&gt;2-&gt;4

Alternatively, you could use a dictionary to map each number to the next number.  Then find the starting point using set differences (between the starting and ending numbers).  The link chain can be assembled by following through the next numbers in the dictionary until there are no next number (for the last entry in the chain):

    links  = [&quot;1-&gt;5&quot;,&quot;2-&gt;4&quot;,&quot;5-&gt;3&quot;,&quot;3-&gt;2&quot;]
    
    nextNum  = dict(link.split(&quot;-&gt;&quot;) for link in links)     # map to next numbers
    chain    = list(set(nextNum)-set(nextNum.values()))[:1] # first number
    chain.extend(filter(None,map(nextNum.get,chain)))       # follow links to end
    
    print(*chain,sep=&quot;-&gt;&quot;)
    # 1-&gt;5-&gt;3-&gt;2-&gt;4


</details>