根据lis中的元组排列人员

Question

一群学生需要排队参加一个活动的游行。我们只有每对相邻的学生的信息。我们使用一个元组列表来表示这个排列信息：列表中的每个元素都是一个元组，其中包含一个学生的名字（称他/她为a）和a后面的学生的名字

例如，^{cd1>}表示Bob在Alice后面。列表[("Alice", "Bob"), ("Bob", "Chris")]表示鲍勃在爱丽丝后面，克里斯在鲍勃后面。你知道吗

对于排在最后的学生，我们用一个空字符串来表示这个学生后面没有人。例如，（“Darren”，“”）表示Darren后面没有人，即Darren在队伍的末尾。你知道吗

给定一个元组列表，其中包含相邻的每对学生的排列信息，实现一个函数，根据学生在排列中的顺序返回列表中的学生。你知道吗

我只能用下面的代码得到第一个和最后一个，但我不能让整个小组都进去。你知道吗

def get_lineup(a_list):
    lst_of_names = []
    output_lst = []
    if len(a_list) == 0:
        return []
    for i in range(len(a_list)):
        for j in range(len(a_list[i])):

            lst_of_names.append(a_list[i][j])
    for k in range(len(lst_of_names)):
        if lst_of_names.count(lst_of_names[k]) == 1 and lst_of_names[k] != "":
            output_lst.append(lst_of_names[k])



    for i in range(len(a_list)):
        if a_list[i][1] == "":
            output_lst.append(a_list[i][0])
    return output_lst

例1：

get_lineup([("Chris", "Darren"), ("Alice", "Bob"), ("Darren", ""), ("Bob", "Chris")]) should return ["Alice", "Bob", "Chris", "Darren"].

例2：

给定以下代码

info = [("Mary", "Jason"), ("John", "Alan"), ("Jason", "George"), ("Alan", "Christie"), ("Christie", "Mary"), ("George", "")]
print(get_lineup(info))

我们应该看到以下输出：

['John', 'Alan', 'Christie', 'Mary', 'Jason', 'George']

Answer 1

我要解决这个问题的方法是从已知的""端点开始反向工作。我们知道最后一个学生和这个标记有关。你知道吗

我使用dict允许代码通过元组返回：

def get_lineup(info):
    rev_info = {pair[1]:pair[0] for pair in info}
    last = rev_info['']
    rev_order = []
    while True:
        rev_order.append(last)
        if last in rev_info:
            last = rev_info[last]
        else:
            return rev_order[::-1]

info = [("Mary", "Jason"), ("John", "Alan"), ("Jason", "George"), ("Alan", "Christie"), ("Christie", "Mary"), ("George", "")]
print(get_lineup(info))

输出：

['John', 'Alan', 'Christie', 'Mary', 'Jason', 'George']

Answer 2

这里有一个可能的解决方案，使用递归。你知道吗

函数将开始填充队列中最后一个人的列表，该列表由元组的第二个元素为空这一事实标识。你知道吗

我们将反向进行，每次查看第二个元素，并检查它是否与元组的第一个元素匹配。如果存在匹配项，则添加第一个元素。你知道吗

我们重新开始，直到没有什么可添加的了，调用列表上的.reverse()（注意：必须首先调用reverse，因为它应用于list对象并返回None）。然后返回列表）。你知道吗

def extract_names(info, curr):
    for n1, n2 in info:
        if n2 == curr[-1]:
            curr.append(n1)
            return extract_names(info, curr)
    curr.reverse()
    return curr

调用使用两个参数：

curr = [e[0] for e in info if e[1] == ""][0] # getting the last person (George), as it's an indicator we can use
extract_names(info, [curr])

如果这有帮助的话，这里有一些执行的照片：

Inside the function again
CURR ['George']
Match found for George (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason']
Match found for Jason (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason', 'Mary']
Match found for Mary (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason', 'Mary', 'Christie']
Match found for Christie (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason', 'Mary', 'Christie', 'Alan']
Match found for Alan (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason', 'Mary', 'Christie', 'Alan', 'John']

Answer 3

以下是我的解决方案：

def get_lineup(pair_list):
    currnt_person = ""
    line = []
    while True:
        try:            
            currnt_person = [i[0] for i in pair_list if i[1] == currnt_person][0]
            line.insert(0, currnt_person)
        except IndexError:
            return line